Strings Questions for Placement 2026 (with Solutions)

Last Updated: March 2026

---

Overview

Strings are one of the most commonly tested topics in technical interviews. String manipulation involves operations like searching, pattern matching, parsing, and transformation. Mastery of string algorithms is essential for roles at top tech companies, particularly for text processing, compiler design, and web development tasks.

Companies Focused on Strings

• Google: Pattern matching, string parsing, autocomplete systems
• Amazon: Log parsing, string compression, palindrome problems
• Microsoft: Word break, regular expression matching
• Meta: String decoding, group anagrams, longest substring
• Adobe: String editing, wildcard matching
• Uber: Text processing for ride information

---

Core Concepts

String Operations Time Complexity

Operation	Python	Java	C++
Access	O(1)	O(1)	O(1)
Concatenation	O(n+m)	O(n+m)	O(n+m)*
Substring	O(k)	O(k)	O(k)
Search	O(n×m)	O(n×m)	O(n×m)

Important String Algorithms

1. KMP (Knuth-Morris-Pratt): O(n+m) pattern matching
2. Rabin-Karp: Rolling hash for pattern matching
3. Z-Algorithm: Linear time pattern matching
4. Manacher's Algorithm: O(n) palindrome finding
5. Suffix Array/Tree: Advanced string processing
6. Trie: Prefix-based string storage

String Properties in Python

# Strings are immutable in Python
s = "hello"
s[0] = "H"  # TypeError!

# Convert to list for mutability
s_list = list(s)
s_list[0] = "H"
s = "".join(s_list)  # "Hello"

# Slicing: O(k) where k is slice length
substring = s[1:4]

# Common operations
len(s)           # Length
s.find("l")      # First occurrence: O(n)
s.count("l")     # Count occurrences: O(n)
s.split()        # Split by whitespace: O(n)
"-".join(list)   # Join strings: O(total length)

---

20 Frequently Asked Coding Questions

---

Question 1: Reverse a String

Problem: Reverse a string in-place (without using extra space for array of characters).

class Solution:
    def reverseString(self, s):
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

# Driver Code
s = ["h", "e", "l", "l", "o"]
sol = Solution()
sol.reverseString(s)
print(s)  # Output: ['o', 'l', 'l', 'e', 'h']

Time Complexity: O(n)
Space Complexity: O(1)

---

Question 2: Valid Palindrome

Problem: Check if a string is a palindrome, considering only alphanumeric characters.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        
        while left < right:
            # Skip non-alphanumeric characters
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            
            if s[left].lower() != s[right].lower():
                return False
            
            left += 1
            right -= 1
        
        return True

# Driver Code
sol = Solution()
print(sol.isPalindrome("A man, a plan, a canal: Panama"))  # Output: True
print(sol.isPalindrome("race a car"))                       # Output: False

Time Complexity: O(n)
Space Complexity: O(1)

---

Question 3: Valid Anagram

Problem: Determine if two strings are anagrams of each other.

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        return Counter(s) == Counter(t)
    
    # Alternative: Using array (for lowercase letters only)
    def isAnagramArray(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = [0] * 26
        
        for c1, c2 in zip(s, t):
            count[ord(c1) - ord('a')] += 1
            count[ord(c2) - ord('a')] -= 1
        
        return all(x == 0 for x in count)
    
    # Alternative: Sorting
    def isAnagramSort(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

# Driver Code
sol = Solution()
print(sol.isAnagram("anagram", "nagaram"))  # Output: True
print(sol.isAnagram("rat", "car"))          # Output: False

Time Complexity: O(n) using Counter, O(n log n) using sort
Space Complexity: O(1) or O(k) where k is character set size

---

Question 4: Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 0
        
        for right in range(len(s)):
            # Shrink window until no duplicates
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            
            char_set.add(s[right])
            max_length = max(max_length, right - left + 1)
        
        return max_length
    
    # Optimized: Store last seen index
    def lengthOfLongestSubstringOptimized(self, s: str) -> int:
        char_index = {}
        left = 0
        max_length = 0
        
        for right, char in enumerate(s):
            if char in char_index and char_index[char] >= left:
                left = char_index[char] + 1
            
            char_index[char] = right
            max_length = max(max_length, right - left + 1)
        
        return max_length

# Driver Code
s = "abcabcbb"
sol = Solution()
print(sol.lengthOfLongestSubstring(s))  # Output: 3 ("abc")

Time Complexity: O(n)
Space Complexity: O(min(m, n)) where m is charset size

---

Question 5: Longest Palindromic Substring

Problem: Find the longest palindromic substring.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        
        start, end = 0, 0
        
        for i in range(len(s)):
            # Odd length palindromes
            len1 = self._expandAroundCenter(s, i, i)
            # Even length palindromes
            len2 = self._expandAroundCenter(s, i, i + 1)
            
            length = max(len1, len2)
            if length > end - start:
                start = i - (length - 1) // 2
                end = i + length // 2
        
        return s[start:end + 1]
    
    def _expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

# Driver Code
s = "babad"
sol = Solution()
print(sol.longestPalindrome(s))  # Output: "bab" or "aba"

Time Complexity: O(n²)
Space Complexity: O(1)

---

Question 6: Implement strStr() (KMP Algorithm)

Problem: Find the index of the first occurrence of needle in haystack.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        
        # Build LPS (Longest Prefix Suffix) array
        lps = self._buildLPS(needle)
        
        i = 0  # Index for haystack
        j = 0  # Index for needle
        
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                
                if j == len(needle):
                    return i - j
            else:
                if j > 0:
                    j = lps[j - 1]
                else:
                    i += 1
        
        return -1
    
    def _buildLPS(self, pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length > 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps

# Driver Code
haystack = "hello"
needle = "ll"
sol = Solution()
print(sol.strStr(haystack, needle))  # Output: 2

Time Complexity: O(n + m)
Space Complexity: O(m)

---

Question 7: Group Anagrams

Problem: Group anagrams together from an array of strings.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs):
        anagram_map = defaultdict(list)
        
        for s in strs:
            # Use sorted string as key
            key = ''.join(sorted(s))
            anagram_map[key].append(s)
        
        return list(anagram_map.values())
    
    # Alternative: Character count as key
    def groupAnagramsCount(self, strs):
        anagram_map = defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            key = tuple(count)
            anagram_map[key].append(s)
        
        return list(anagram_map.values())

# Driver Code
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
sol = Solution()
print(sol.groupAnagrams(strs))
# Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Time Complexity: O(N × K log K) where N = number of strings, K = max length
Space Complexity: O(N × K)

---

Question 8: Longest Common Prefix

Problem: Find the longest common prefix string among an array of strings.

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        
        # Start with first string as prefix
        prefix = strs[0]
        
        for s in strs[1:]:
            # Reduce prefix until it matches
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        
        return prefix
    
    # Alternative: Vertical scanning
    def longestCommonPrefixVertical(self, strs):
        if not strs:
            return ""
        
        for i, char in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != char:
                    return strs[0][:i]
        
        return strs[0]

# Driver Code
strs = ["flower", "flow", "flight"]
sol = Solution()
print(sol.longestCommonPrefix(strs))  # Output: "fl"

Time Complexity: O(S) where S is sum of all characters
Space Complexity: O(1)

---

Question 9: Zigzag Conversion

Problem: Write string in zigzag pattern and read line by line.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s
        
        # Create list for each row
        rows = [''] * numRows
        current_row = 0
        going_down = False
        
        for char in s:
            rows[current_row] += char
            
            # Change direction at top and bottom
            if current_row == 0 or current_row == numRows - 1:
                going_down = not going_down
            
            current_row += 1 if going_down else -1
        
        return ''.join(rows)

# Driver Code
s = "PAYPALISHIRING"
numRows = 3
sol = Solution()
print(sol.convert(s, numRows))  # Output: "PAHNAPLSIIGYIR"
# P   A   H   N
# A P L S I I G
# Y   I   R

Time Complexity: O(n)
Space Complexity: O(n)

---

Question 10: Decode String

Problem: Decode string with pattern k[encoded_string].

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_string = ""
        current_num = 0
        
        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)
            elif char == '[':
                # Push current state to stack
                stack.append((current_string, current_num))
                current_string = ""
                current_num = 0
            elif char == ']':
                # Pop and decode
                prev_string, num = stack.pop()
                current_string = prev_string + num * current_string
            else:
                current_string += char
        
        return current_string

# Driver Code
s = "3[a]2[bc]"
sol = Solution()
print(sol.decodeString(s))  # Output: "aaabcbc"

s2 = "3[a2[c]]"
print(sol.decodeString(s2))  # Output: "accaccacc"

Time Complexity: O(maxK × n) where maxK is maximum number
Space Complexity: O(n)

---

Question 11: Minimum Window Substring

Problem: Find minimum window in S which contains all characters in T.

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        
        # Count characters needed
        need = Counter(t)
        required = len(need)
        
        # Count characters in current window
        window = {}
        formed = 0
        
        left = 0
        min_len = float('inf')
        min_window = ""
        
        for right, char in enumerate(s):
            window[char] = window.get(char, 0) + 1
            
            if char in need and window[char] == need[char]:
                formed += 1
            
            # Try to shrink window
            while formed == required and left <= right:
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_window = s[left:right + 1]
                
                window[s[left]] -= 1
                if s[left] in need and window[s[left]] < need[s[left]]:
                    formed -= 1
                left += 1
        
        return min_window

# Driver Code
s = "ADOBECODEBANC"
t = "ABC"
sol = Solution()
print(sol.minWindow(s, t))  # Output: "BANC"

Time Complexity: O(|S| + |T|)
Space Complexity: O(|S| + |T|)

---

Question 12: Word Break

Problem: Determine if string can be segmented into dictionary words.

class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        word_set = set(wordDict)
        n = len(s)
        
        # dp[i] = True if s[:i] can be segmented
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True
                    break
        
        return dp[n]
    
    # Optimized: Only check valid word lengths
    def wordBreakOptimized(self, s: str, wordDict) -> bool:
        word_set = set(wordDict)
        word_lengths = set(len(word) for word in wordDict)
        n = len(s)
        
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(1, n + 1):
            for length in word_lengths:
                if i >= length and dp[i - length]:
                    if s[i - length:i] in word_set:
                        dp[i] = True
                        break
        
        return dp[n]

# Driver Code
s = "leetcode"
wordDict = ["leet", "code"]
sol = Solution()
print(sol.wordBreak(s, wordDict))  # Output: True

Time Complexity: O(n × m × k) where n = len(s), m = len(wordDict), k = avg word length
Space Complexity: O(n)

---

Question 13: Regular Expression Matching

Problem: Implement regular expression matching with '.' and '*'.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        
        # dp[i][j] = True if s[:i] matches p[:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        # Handle patterns like a*, a*b*, etc.
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '.' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    # Zero occurrences of preceding character
                    dp[i][j] = dp[i][j - 2]
                    
                    # One or more occurrences
                    if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
        
        return dp[m][n]

# Driver Code
s = "aa"
p = "a*"
sol = Solution()
print(sol.isMatch(s, p))  # Output: True

Time Complexity: O(m × n)
Space Complexity: O(m × n)

---

Question 14: Wildcard Matching

Problem: Implement wildcard matching with '?' and '*'.

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        
        # dp[i][j] = True if s[:i] matches p[:j]
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        
        # Handle leading stars
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    # * matches empty or one or more characters
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        
        return dp[m][n]
    
    # Space optimized: O(n)
    def isMatchOptimized(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        prev = [False] * (n + 1)
        prev[0] = True
        
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                prev[j] = prev[j - 1]
        
        for i in range(1, m + 1):
            curr = [False] * (n + 1)
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    curr[j] = curr[j - 1] or prev[j]
                elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
                    curr[j] = prev[j - 1]
            prev = curr
        
        return prev[n]

# Driver Code
s = "aa"
p = "*"
sol = Solution()
print(sol.isMatch(s, p))  # Output: True

Time Complexity: O(m × n)
Space Complexity: O(m × n) or O(n) optimized

---

Question 15: Count and Say

Problem: Generate the nth term of count-and-say sequence.

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        
        prev = self.countAndSay(n - 1)
        result = []
        count = 1
        
        for i in range(1, len(prev)):
            if prev[i] == prev[i - 1]:
                count += 1
            else:
                result.append(str(count))
                result.append(prev[i - 1])
                count = 1
        
        # Append last group
        result.append(str(count))
        result.append(prev[-1])
        
        return ''.join(result)
    
    # Iterative approach
    def countAndSayIterative(self, n: int) -> str:
        result = "1"
        
        for _ in range(n - 1):
            current = []
            count = 1
            
            for i in range(1, len(result)):
                if result[i] == result[i - 1]:
                    count += 1
                else:
                    current.append(str(count))
                    current.append(result[i - 1])
                    count = 1
            
            current.append(str(count))
            current.append(result[-1])
            result = ''.join(current)
        
        return result

# Driver Code
n = 4
sol = Solution()
print(sol.countAndSay(n))  # Output: "1211"
# 1 -> "11" -> "21" -> "1211"

Time Complexity: O(n × m) where m is length of string
Space Complexity: O(m)

---

Question 16: Edit Distance

Problem: Find minimum operations to convert word1 to word2.

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        
        # dp[i][j] = min distance between word1[:i] and word2[:j]
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Base cases
        for i in range(m + 1):
            dp[i][0] = i  # Delete all characters
        for j in range(n + 1):
            dp[0][j] = j  # Insert all characters
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # Insert, Delete, Replace
                    dp[i][j] = 1 + min(dp[i][j - 1],    # Insert
                                      dp[i - 1][j],     # Delete
                                      dp[i - 1][j - 1]) # Replace
        
        return dp[m][n]
    
    # Space optimized: O(n)
    def minDistanceOptimized(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        prev = list(range(n + 1))
        
        for i in range(1, m + 1):
            curr = [i] + [0] * n
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = 1 + min(curr[j - 1], prev[j], prev[j - 1])
            prev = curr
        
        return prev[n]

# Driver Code
word1 = "horse"
word2 = "ros"
sol = Solution()
print(sol.minDistance(word1, word2))  # Output: 3
# horse -> rorse -> rose -> ros

Time Complexity: O(m × n)
Space Complexity: O(m × n) or O(n) optimized

---

Question 17: Permutation in String

Problem: Check if s2 contains a permutation of s1.

from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        # Character counts
        s1_count = [0] * 26
        window_count = [0] * 26
        
        for i in range(len(s1)):
            s1_count[ord(s1[i]) - ord('a')] += 1
            window_count[ord(s2[i]) - ord('a')] += 1
        
        # Slide window
        for i in range(len(s1), len(s2)):
            if s1_count == window_count:
                return True
            
            # Add new character
            window_count[ord(s2[i]) - ord('a')] += 1
            # Remove old character
            window_count[ord(s2[i - len(s1)]) - ord('a')] -= 1
        
        return s1_count == window_count

# Driver Code
s1 = "ab"
s2 = "eidbaooo"
sol = Solution()
print(sol.checkInclusion(s1, s2))  # Output: True

Time Complexity: O(n)
Space Complexity: O(1) - Fixed size array

---

Question 18: Integer to Roman

Problem: Convert integer to Roman numeral.

class Solution:
    def intToRoman(self, num: int) -> str:
        # Value to symbol mapping
        val_sym_pairs = [
            (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
            (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
            (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")
        ]
        
        result = []
        
        for value, symbol in val_sym_pairs:
            while num >= value:
                result.append(symbol)
                num -= value
        
        return ''.join(result)

# Driver Code
num = 58
sol = Solution()
print(sol.intToRoman(num))  # Output: "LVIII"

Time Complexity: O(1) - Limited iterations
Space Complexity: O(1)

---

Question 19: Roman to Integer

Problem: Convert Roman numeral to integer.

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_map = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        
        result = 0
        n = len(s)
        
        for i in range(n):
            # If current value < next value, subtract it
            if i < n - 1 and roman_map[s[i]] < roman_map[s[i + 1]]:
                result -= roman_map[s[i]]
            else:
                result += roman_map[s[i]]
        
        return result

# Driver Code
s = "MCMXCIV"
sol = Solution()
print(sol.romanToInt(s))  # Output: 1994

Time Complexity: O(n)
Space Complexity: O(1)

---

Question 20: Multiply Strings

Problem: Multiply two non-negative integers represented as strings.

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == "0" or num2 == "0":
            return "0"
        
        m, n = len(num1), len(num2)
        result = [0] * (m + n)
        
        # Multiply digit by digit
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                sum_val = mul + result[i + j + 1]
                
                result[i + j + 1] = sum_val % 10
                result[i + j] += sum_val // 10
        
        # Convert to string
        i = 0
        while i < len(result) and result[i] == 0:
            i += 1
        
        return ''.join(str(x) for x in result[i:])

# Driver Code
num1 = "123"
num2 = "456"
sol = Solution()
print(sol.multiply(num1, num2))  # Output: "56088"

Time Complexity: O(m × n)
Space Complexity: O(m + n)

---

MCQ Questions

Question 1

What is the time complexity of the KMP pattern matching algorithm?

• A) O(n × m)
• B) O(n + m)
• C) O(n log m)
• D) O(n²)

---

Question 2

What data structure is most efficient for prefix matching?

• A) Hash Table
• B) Trie
• C) Binary Search Tree
• D) Array

---

Question 3

In Python, what is the time complexity of string concatenation using +?

• A) O(1)
• B) O(n)
• C) O(n²) for n concatenations
• D) O(log n)

---

Question 4

Which algorithm finds the longest palindromic substring in O(n²) time?

• A) Manacher's Algorithm
• B) Expand Around Center
• C) KMP Algorithm
• D) Rabin-Karp

---

Question 5

What is the space complexity of the Z-algorithm for pattern matching?

• A) O(n × m)
• B) O(n + m)
• C) O(n)
• D) O(1)

---

Interview Tips for Strings

1. Know your string operations: Understand time complexity of common operations in your language

2. Key algorithms to master:

   • KMP for pattern matching
   • Sliding window for substring problems
   • Dynamic programming for edit distance, palindromes
   • Trie for prefix-based problems

3. Common patterns:

   • Two pointers (palindrome, reverse)
   • Sliding window (substring problems)
   • Hash map (anagrams, character count)
   • DP (edit distance, regex matching)

4. Language-specific tips:

   • Python: strings are immutable, use list for modifications
   • Java: use StringBuilder for concatenation
   • C++: strings are mutable

5. Edge cases to consider:

   • Empty string
   • Single character
   • All same characters
   • Special characters and spaces
   • Unicode/ASCII differences

---

Frequently Asked Questions

Q1: How do I check if two strings are anagrams efficiently?

A: Use character counting with a fixed-size array (26 for lowercase letters) or a hash map. This gives O(n) time and O(1) or O(k) space.

Q2: What is the most efficient way to reverse a string?

A: In Python: s[::-1]. For in-place reversal, use two pointers swapping from ends.

Q3: How does KMP algorithm achieve O(n+m) complexity?

A: KMP preprocesses the pattern to create an LPS (Longest Prefix Suffix) array. This avoids re-checking characters that we already know match.

Q4: What is the difference between substring and subsequence?

A: A substring consists of consecutive characters from the original string. A subsequence can skip characters but maintains order.

Q5: When should I use a Trie vs Hash Map for string problems?

A: Use Trie for prefix-based operations (autocomplete, prefix search). Use Hash Map for exact match lookups.

---

Master these string problems and algorithms to excel in technical interviews. Practice implementing KMP and other core algorithms from scratch.