PRACTICE • LEARN • GROW
Strings MCQs
Solve topic-wise placement questions and improve your skills.
Strings Progress
0 of 40 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What is the time complexity of building the Longest Prefix Suffix (LPS) array in the KMP algorithm for a pattern of length M?
A.
O(M)
B.
O(M^2)
C.
O(M log M)
D.
O(2^M)
Explanation & Key
Correct Answer:
2
Which data structure is most optimal for searching words with a shared prefix in dictionary auto-completion?
A.
Binary Search Tree
B.
Trie (Prefix Tree)
C.
Hash Table with separate chaining
D.
Max-Heap
Explanation & Key
Correct Answer:
3
Why are String objects immutable in Java?
A.
To decrease heap memory size
B.
Because arrays are dynamic in Java
C.
To support String pool caching, thread-safety, and secure hashing
D.
To allow primitive type conversions without casting
Explanation & Key
Correct Answer:
4
What technique does the Rabin-Karp pattern searching algorithm use to compare substrings quickly?
A.
Suffix automaton transitions
B.
Depth-first search with memoization
C.
Dynamic programming matrix multiplication
D.
Sliding window with rolling hash
Explanation & Key
Correct Answer:
5
What is the minimum auxiliary space needed to verify if two strings are anagrams of each other (assuming lowercase English letters)?
A.
O(1)
B.
O(N)
C.
O(N log N)
D.
O(N^2)
Explanation & Key
Correct Answer:
6
What is the time complexity of Manacher's algorithm for finding the longest palindromic substring in a string of length N?
A.
O(N log N)
B.
O(N)
C.
O(N^2)
D.
O(N sqrt(N))
Explanation & Key
Correct Answer:
7
Which algorithm is best suited for finding all occurrences of multiple pattern strings simultaneously in a text?
A.
Boyer-Moore Algorithm
B.
KMP Algorithm
C.
Aho-Corasick Automaton
D.
Rabin-Karp with single hash
Explanation & Key
Correct Answer:
8
In the Boyer-Moore string search algorithm, which two heuristics determine the shift of the pattern?
A.
Prefix Heuristic and Rolling Hash Heuristic
B.
Longest Common Subsequence and Longest Prefix
C.
Hamming Distance and Levenshtein Distance
D.
Bad Character Heuristic and Good Suffix Heuristic
Explanation & Key
Correct Answer:
9
What is the space complexity of storing N strings each of length L in a standard Trie with alphabet size Sigma?
A.
O(N * L * Sigma)
B.
O(N + L + Sigma)
C.
O(Sigma^L)
D.
O(N * Sigma)
Explanation & Key
Correct Answer:
10
What is the time complexity to check if a string of length N is a palindrome using two pointers?
A.
O(log N)
B.
O(N)
C.
O(N^2)
D.
O(1)
Explanation & Key
Correct Answer:
11
Which data structure can be used to solve the "Longest Substring Without Repeating Characters" in O(N) time?
A.
Stack and Binary Search
B.
Disjoint Set Union (DSU)
C.
Sliding window with a Hash Map / Frequency Table
D.
Min-Priority Queue
Explanation & Key
Correct Answer:
12
What does the Z-array in the Z-algorithm store for an index i?
A.
The number of distinct characters up to index i
B.
Length of the longest suffix ending at s[i]
C.
The hash value of substring s[0...i]
D.
Length of the longest substring starting from s[i] that is also a prefix of s
Explanation & Key
Correct Answer:
13
What is the result of applying run-length encoding (RLE) on the string "WWWWWWBBWWWW"?
A.
W6B2W4
B.
6W2B4W
C.
W12B2
D.
6WB4W
Explanation & Key
Correct Answer:
14
What is the Edit Distance (Levenshtein Distance) between "kitten" and "sitting"?
A.
2
B.
3
C.
4
D.
5
Explanation & Key
Correct Answer:
15
In Python, what happens when you perform string concatenation in a loop using the += operator?
A.
Strings are modified in-place with zero reallocation
B.
Python automatically converts strings to linked lists
C.
It creates a new string object each time, leading to O(N^2) total complexity
D.
It throws a TypeError because strings cannot be concatenated
Explanation & Key
Correct Answer:
16
Which representation of strings compresses long chains of single-child nodes in a Trie into single edges?
A.
Splay Tree
B.
B-Tree
C.
Fenwick Tree
D.
Radix Tree (Patricia Trie)
Explanation & Key
Correct Answer:
17
What is the time complexity to find all palindromic partitions of a string of length N in the worst case?
A.
O(N * 2^N)
B.
O(N^2)
C.
O(N^3)
D.
O(N!)
Explanation & Key
Correct Answer:
18
Which algorithm is typically used to find the Longest Common Prefix (LCP) of an array of strings in O(S) where S is sum of all characters?
A.
Floyd-Warshall algorithm
B.
Character by character horizontal or vertical scanning
C.
Topological sorting
D.
Bellman-Ford algorithm
Explanation & Key
Correct Answer:
19
How can you check if string S2 is a rotation of string S1?
A.
Sort both strings and compare
B.
Reverse S1 and check equality with S2
C.
Check if S1.length == S2.length and S2 is a substring of (S1 + S1)
D.
Compute XOR of all characters
Explanation & Key
Correct Answer:
20
What is the primary advantage of Suffix Trees over Suffix Arrays?
A.
Suffix Trees use significantly less memory than Suffix Arrays
B.
Suffix Trees can be built in O(1) time
C.
Suffix Trees do not support pattern matching
D.
Suffix Trees can be visualized as trees, but Suffix Arrays are faster and use 3-5x less memory
Explanation & Key
Correct Answer:
21
In C++, what does the `std::string_view` class provide?
A.
A non-owning, lightweight view of a character sequence avoiding heap allocations
B.
A mutable deep copy of string data
C.
A thread-safe synchronized string wrapper
D.
A regular expression parser for strings
Explanation & Key
Correct Answer:
22
What is the optimal algorithm to find the minimum number of character deletions to make a string an anagram of another string?
A.
Backtracking with recursion
B.
Counting character frequencies and summing absolute differences of frequencies
C.
Dynamic Programming Edit Distance
D.
Sorting both and performing binary search
Explanation & Key
Correct Answer:
23
What is the maximum number of distinct substrings in a string of length N consisting of all identical characters (e.g., "aaaa")?
A.
N * (N + 1) / 2
B.
2^N
C.
N
D.
N^2
Explanation & Key
Correct Answer:
24
Which problem can be solved using the Boyer-Moore Majority Voting algorithm on strings/characters?
A.
Finding the longest common subsequence
B.
Sorting characters in lexicographical order
C.
Computing the hash value of a string
D.
Finding the character that appears more than N/2 times in O(N) time and O(1) space
Explanation & Key
Correct Answer:
25
What is the worst-case time complexity of the Naive String Matching algorithm when text length is N and pattern length is M?
A.
O(N * M)
B.
O(N + M)
C.
O(N log M)
D.
O(M log N)
Explanation & Key
Correct Answer:
26
What is the time complexity of building the Longest Proper Prefix which is also a Suffix (LPS) array in the KMP algorithm for a pattern of length m?
A.
O(m^2)
B.
O(m)
C.
O(m log m)
D.
O(2^m)
Explanation & Key
Correct Answer:
27
What is the average time complexity of the Rabin-Karp substring search algorithm for text length n and pattern length m?
A.
O(n * m)
B.
O(n + m)
C.
O(log(n + m))
D.
O(n^2)
Explanation & Key
Correct Answer:
28
What is the purpose of using a prime modulus in polynomial rolling hash functions?
A.
To make the output string uppercase
B.
To distribute hash values uniformly across the range and minimize hash collisions
C.
To prevent integer underflow
D.
To guarantee strings can be reversed
Explanation & Key
Correct Answer:
29
How can you check if two strings s and t are valid anagrams of each other in O(n) time and O(1) auxiliary space?
A.
Sort both strings and compare
B.
Use a fixed-size frequency array of 26 integers to count characters
C.
Generate all permutations of s and search for t
D.
Compute their ASCII sum only
Explanation & Key
Correct Answer:
30
What is the time complexity of Manacher's Algorithm for finding the longest palindromic substring?
A.
O(n^2)
B.
O(n log n)
C.
O(n)
D.
O(n^3)
Explanation & Key
Correct Answer:
31
In C++, why is pass-by-value `void process(string s)` considered an antipattern for large strings compared to `void process(const string& s)`?
A.
Because pass-by-value deep copies the entire character buffer from the heap, consuming O(n) time and memory
B.
Because pass-by-value causes a compile error
C.
Because pass-by-value converts strings to uppercase
D.
Because references cannot be used in loops
Explanation & Key
Correct Answer:
32
What is the length of the LPS array for pattern "AABAACAABAA"?
A.
11
B.
5
C.
9
D.
0
Explanation & Key
Correct Answer:
33
What is the Z-algorithm used for in string processing?
A.
String compression
B.
Finding the length of the longest substring starting from s[i] that is also a prefix of s, in O(n) time
C.
Sorting strings alphabetically
D.
Validating JSON strings
Explanation & Key
Correct Answer:
34
In the Boyer-Moore string search algorithm, what are the two heuristic rules used to skip text alignments?
A.
Bad Character Rule and Good Suffix Rule
B.
Prefix Rule and Suffix Rule
C.
Rolling Hash and Bloom Filter
D.
Alphabet Rule and Length Rule
Explanation & Key
Correct Answer:
35
What is the time complexity of checking whether a string s of length n is a rotation of string t of length n?
A.
O(n^2)
B.
O(n) by checking if t is a substring of (s + s)
C.
O(n log n)
D.
O(1)
Explanation & Key
Correct Answer:
36
What is Small String Optimization (SSO) in modern C++ standard libraries?
A.
A compiler flag that deletes short strings
B.
Storing strings shorter than ~15-22 characters directly inside the string object buffer on the stack to eliminate heap allocation
C.
Compressing strings using Huffman coding
D.
Preventing strings from exceeding 100 characters
Explanation & Key
Correct Answer:
37
What is the longest palindromic substring of "babad"?
A.
"bab" or "aba"
B.
"babad"
C.
"bad"
D.
"d"
Explanation & Key
Correct Answer:
38
What is the time complexity to find the longest common prefix among an array of N strings, each of maximum length L?
A.
O(N * L)
B.
O(N^2 * L)
C.
O(L log N)
D.
O(2^(N + L))
Explanation & Key
Correct Answer:
39
Which string algorithm is best suited for searching a dictionary of 100,000 patterns simultaneously within a single large document?
A.
Repeated KMP for each pattern
B.
Aho-Corasick Automaton
C.
Naive substring search
D.
Linear scan with std::string::find
Explanation & Key
Correct Answer:
40
How do you reverse the words in a sentence (e.g. "the sky is blue" -> "blue is sky the") in O(1) extra space?
A.
Reverse the entire string, then reverse each individual word within the string
B.
Split words into a stack and pop them
C.
Store words in a vector and print backward
D.
Use a double-ended queue
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
