Most Asked String Coding Problems for Programming Interviews

Strings are a fundamental data type in programming, and they appear in almost every technical interview—whether you’re interviewing for a role at FAANG, a startup, or a tech giant. Mastering string manipulation not only demonstrates your problem-solving skills but also your ability to handle real-world scenarios (e.g., text processing, data validation, and parsing).

In this blog, we’ll break down the 10 most commonly asked string coding problems in interviews, complete with problem statements, step-by-step approaches, Python solutions, time/space complexity analysis, and edge cases. By the end, you’ll have a clear roadmap to tackle these problems confidently.

Table of Contents#

  1. Reverse a String
  2. Check if a String is a Palindrome
  3. Check for Anagrams
  4. Longest Substring Without Repeating Characters
  5. String Compression
  6. Valid Parentheses
  7. Longest Palindromic Substring
  8. Implement strstr()
  9. Convert String to Integer (atoi)
  10. Count and Say Sequence
  11. Conclusion
  12. References

1. Reverse a String#

Problem Statement#

Given a string, reverse the characters of the string in-place (if possible) or return a new reversed string.

Approach#

The simplest approach is the two-pointer technique:

  • Use two pointers, left starting at the beginning (index 0) and right at the end (index len(s)-1).
  • Swap the characters at left and right.
  • Move left forward and right backward until they meet.

For immutable strings (e.g., Python strings), convert the string to a list (mutable), reverse it, then join back to a string.

Solution Code#

def reverse_string(s):
    # Convert string to list for mutability (Python-specific)
    s_list = list(s)
    left, right = 0, len(s_list) - 1
    while left < right:
        # Swap characters
        s_list[left], s_list[right] = s_list[right], s_list[left]
        left += 1
        right -= 1
    return ''.join(s_list)
 
# Example usage:
print(reverse_string("hello"))  # Output: "olleh"

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. We swap n/2 pairs of characters.
  • Space Complexity: O(n) (for Python, since strings are immutable and we create a list). For mutable strings (e.g., C++ std::string), space is O(1) (in-place reversal).

Edge Cases#

  • Empty string ("" → "").
  • Single-character string ("a" → "a").
  • String with all identical characters ("aaaaa" → "aaaaa").

2. Check if a String is a Palindrome#

Problem Statement#

A palindrome reads the same forwards and backwards. Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Approach#

  1. Filter Alphanumeric Characters: Remove non-alphanumeric characters (e.g., spaces, punctuation) and convert to lowercase.
  2. Two-Pointer Check: Use two pointers to compare characters from the start and end moving inward. If all pairs match, it’s a palindrome.

Solution Code#

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        # Move left pointer to next alphanumeric character
        while left < right and not s[left].isalnum():
            left += 1
        # Move right pointer to previous alphanumeric character
        while left < right and not s[right].isalnum():
            right -= 1
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
# Example usage:
print(is_palindrome("A man, a plan, a canal: Panama"))  # Output: True
print(is_palindrome("race a car"))  # Output: False

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. We traverse the string once.
  • Space Complexity: O(1), as we use constant extra space.

Edge Cases#

  • Empty string ("" → considered a palindrome).
  • String with only non-alphanumeric characters ("!!!$$$" → considered a palindrome).
  • Case sensitivity ("AbBa" → palindrome after lowercasing).

3. Check for Anagrams#

Problem Statement#

Two strings are anagrams if they contain the same characters in the same frequency (e.g., "listen" and "silent" are anagrams).

Approach#

Approach 1: Sort and Compare

  • Sort both strings. If they are anagrams, the sorted versions will be identical.

Approach 2: Hash Map (Character Count)

  • Count the frequency of each character in both strings using a hash map (or array for fixed character sets like lowercase letters).
  • If the counts match for all characters, the strings are anagrams.

Solution Code (Hash Map Approach)#

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False  # Anagrams must have the same length
    
    # Initialize count array for 26 lowercase letters
    count = [0] * 26
    for char in s:
        count[ord(char.lower()) - ord('a')] += 1
    for char in t:
        count[ord(char.lower()) - ord('a')] -= 1
        if count[ord(char.lower()) - ord('a')] < 0:
            return False  # Extra character in t
    
    return all(c == 0 for c in count)
 
# Example usage:
print(is_anagram("listen", "silent"))  # Output: True
print(is_anagram("hello", "bello"))    # Output: False

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the strings. We traverse each string once.
  • Space Complexity: O(1) (for fixed character sets like lowercase letters, the count array size is constant).

Edge Cases#

  • Strings of different lengths (immediately return False).
  • Case sensitivity (e.g., "Listen" vs "silent"—convert to lowercase first).
  • Empty strings ("" and "" → anagrams).

4. Longest Substring Without Repeating Characters#

Problem Statement#

Given a string, find the length of the longest substring without repeating characters.

Approach#

Sliding Window with Hash Map:

  • Use a sliding window defined by two pointers, left and right (initially 0).
  • Expand the window by moving right and track the last occurrence of each character using a hash map.
  • If a character repeats (i.e., exists in the map and its last index ≥ left), move left to last_index + 1 to exclude the repeated character.
  • Update the maximum length of the window as right - left + 1.

Solution Code#

def length_of_longest_substring(s: str) -> int:
    char_map = {}  # Stores last index of each character
    max_len = 0
    left = 0
    
    for right in range(len(s)):
        char = s[right]
        # If char is in map and its last index is within the current window
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1  # Move left to exclude the duplicate
        char_map[char] = right  # Update last index of current char
        current_len = right - left + 1
        max_len = max(max_len, current_len)
    
    return max_len
 
# Example usage:
print(length_of_longest_substring("abcabcbb"))  # Output: 3 ("abc")
print(length_of_longest_substring("bbbbb"))     # Output: 1 ("b")

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. Each character is processed once.
  • Space Complexity: O(min(m, n)), where m is the size of the character set (e.g., 256 for ASCII).

Edge Cases#

  • All unique characters ("abcd" → length 4).
  • All repeating characters ("aaaaa" → length 1).
  • Empty string ("" → length 0).

5. String Compression#

Problem Statement#

Compress a string by replacing consecutive duplicate characters with the character followed by the count (e.g., "aabcccccaaa" → "a2b1c5a3"). If the compressed string is not shorter than the original, return the original string.

Approach#

  1. Iterate and Count Consecutive Characters: Traverse the string, counting consecutive occurrences of each character.
  2. Build Compressed String: Append the character and its count (if count > 1) to a result list (for efficient string concatenation).
  3. Compare Lengths: If the compressed string’s length is ≥ original, return the original string; otherwise, return the compressed string.

Solution Code#

def compress(chars):
    n = len(chars)
    if n <= 1:
        return n  # No compression possible
    
    result = []
    count = 1
    for i in range(1, n):
        if chars[i] == chars[i-1]:
            count += 1
        else:
            result.append(chars[i-1])
            if count > 1:
                result.extend(list(str(count)))
            count = 1
    # Add the last character and its count
    result.append(chars[-1])
    if count > 1:
        result.extend(list(str(count)))
    
    # Update the input list (in-place for LeetCode problem)
    compressed = ''.join(result)
    if len(compressed) >= n:
        return n  # Return original length if no compression
    chars[:len(compressed)] = compressed
    return len(compressed)
 
# Example usage:
chars = ["a","a","b","b","c","c","c"]
print(compress(chars))  # Output: 6 (compressed to ["a","2","b","2","c","3"])

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. We traverse the string once.
  • Space Complexity: O(n) (for storing the result list; in-place compression reduces this to O(1) for the output, but the result list is needed temporarily).

Edge Cases#

  • Single character ("a" → return "a").
  • All unique characters ("abcd" → compressed is "a1b1c1d1" (longer than original, return original).
  • Count > 9 ("aaaaaaaaaa" → "a10").

6. Valid Parentheses#

Problem Statement#

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A valid string must:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Approach#

Stack-Based Validation:

  • Use a stack to track opening brackets.
  • For each closing bracket, check if the top of the stack is the matching opening bracket. If not, return False.
  • If the stack is empty after processing all characters, return True; otherwise, return False.

Solution Code#

def is_valid(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    for char in s:
        if char in bracket_map:  # Closing bracket
            top = stack.pop() if stack else '#'
            if bracket_map[char] != top:
                return False
        else:  # Opening bracket
            stack.append(char)
    
    return not stack  # Stack must be empty for valid string
 
# Example usage:
print(is_valid("()[]{}"))  # Output: True
print(is_valid("(]"))      # Output: False

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. We process each character once.
  • Space Complexity: O(n) in the worst case (all opening brackets, stack size = n).

Edge Cases#

  • Empty string ("" → valid).
  • Single bracket ("(" → invalid).
  • Mismatched brackets ("([)]" → invalid).

7. Longest Palindromic Substring#

Problem Statement#

Given a string, return the longest palindromic substring (a substring that reads the same forwards and backwards).

Approach#

Expand Around Center:

  • Palindromes can have odd or even lengths. For each character (odd length) and between each pair of characters (even length), expand outward as long as the substring remains a palindrome.
  • Track the start and end indices of the longest palindrome found.

Solution Code#

def longest_palindrome(s: str) -> str:
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Return the palindrome substring (left+1 to right-1)
        return s[left+1:right]
    
    longest = ""
    for i in range(len(s)):
        # Odd length palindromes (center at i)
        odd_pali = expand_around_center(i, i)
        # Even length palindromes (center between i and i+1)
        even_pali = expand_around_center(i, i+1)
        
        # Update longest palindrome
        if len(odd_pali) > len(longest):
            longest = odd_pali
        if len(even_pali) > len(longest):
            longest = even_pali
    
    return longest
 
# Example usage:
print(longest_palindrome("babad"))  # Output: "bab" or "aba"
print(longest_palindrome("cbbd"))   # Output: "bb"

Time/Space Complexity#

  • Time Complexity: O(n²), where n is the length of the string. For each of the n centers, we expand up to n times.
  • Space Complexity: O(1), as we use constant extra space (excluding the output).

Edge Cases#

  • Single character ("a" → "a").
  • All characters the same ("aaaaa" → "aaaaa").
  • No palindrome longer than 1 ("abc" → "a", "b", or "c").

8. Implement strstr()#

Problem Statement#

Implement the strstr() function, which returns the index of the first occurrence of a substring (needle) in a string (haystack). If the needle is not found, return -1.

Approach#

Brute Force:

  • Iterate through the haystack from index i=0 to len(haystack)-len(needle).
  • For each i, check if the substring haystack[i:i+len(needle)] matches the needle.

Optimization: Use the Knuth-Morris-Pratt (KMP) algorithm for linear time complexity, but brute force is simpler for small inputs.

Solution Code (Brute Force)#

def str_str(haystack: str, needle: str) -> int:
    len_haystack = len(haystack)
    len_needle = len(needle)
    
    if len_needle == 0:
        return 0  # Edge case: empty needle
    
    # Iterate through possible starting positions in haystack
    for i in range(len_haystack - len_needle + 1):
        # Check if substring matches needle
        if haystack[i:i+len_needle] == needle:
            return i
    return -1
 
# Example usage:
print(str_str("hello", "ll"))      # Output: 2
print(str_str("aaaaa", "bba"))     # Output: -1

Time/Space Complexity#

  • Time Complexity: O((n-m+1)*m), where n is the length of haystack and m is the length of needle. In the worst case (e.g., haystack = "aaaaa", needle = "aaab"), we check O(n) positions, each taking O(m) time.
  • Space Complexity: O(1), as we use constant extra space.

Edge Cases#

  • Empty needle (return 0, per C library conventions).
  • needle longer than haystack (return -1).
  • needle at the start/end of haystack.

9. Convert String to Integer (atoi)#

Problem Statement#

Implement the atoi function, which converts a string to a 32-bit signed integer. The function should handle:

  • Leading whitespace.
  • Optional sign (+ or -).
  • Numeric digits (ignore non-digit characters after digits).
  • Overflow (clamp to INT_MIN (-2³¹) or INT_MAX (2³¹ - 1)).

Approach#

  1. Trim Whitespace: Skip leading spaces.
  2. Check Sign: Determine if the number is positive or negative.
  3. Extract Digits: Iterate through the string, collecting digits until a non-digit is encountered.
  4. Handle Overflow: Convert digits to an integer and clamp to INT_MIN/INT_MAX if overflow occurs.

Solution Code#

def my_atoi(s: str) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    # Step 1: Trim leading whitespace
    s = s.strip()
    if not s:
        return 0
    
    # Step 2: Check sign
    sign = 1
    index = 0
    if s[0] in '+-':
        sign = -1 if s[0] == '-' else 1
        index += 1
    
    # Step 3: Extract digits and convert to integer
    num = 0
    while index < len(s) and s[index].isdigit():
        digit = int(s[index])
        # Step 4: Check overflow before updating num
        if num > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        num = num * 10 + digit
        index += 1
    
    return num * sign
 
# Example usage:
print(my_atoi("   -42"))          # Output: -42
print(my_atoi("4193 with words")) # Output: 4193
print(my_atoi("91283472332"))    # Output: 2147483647 (INT_MAX)

Time/Space Complexity#

  • Time Complexity: O(n), where n is the length of the string. We traverse the string once.
  • Space Complexity: O(1), as we use constant extra space.

Edge Cases#

  • All whitespace (" " → 0).
  • Non-digit characters before digits ("words and 987" → 0).
  • Decimal points ("3.14159" → 3).
  • Overflow/underflow ("2147483648" → INT_MAX, "-2147483649" → INT_MIN).

10. Count and Say Sequence#

Problem Statement#

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

  • countAndSay(1) = "1"
  • countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

For example:

  • n=1 → "1"
  • n=2 → "one 1" → "11"
  • n=3 → "two 1s" → "21"
  • n=4 → "one 2, one 1" → "1211"

Approach#

Iterative Generation:

  • Start with the base case (n=1 → "1").
  • For each i from 2 to n, generate the i-th term by "saying" the (i-1)-th term:
    • Iterate through the previous term, counting consecutive digits.
    • Append the count followed by the digit to build the new term.

Solution Code#

def count_and_say(n: int) -> str:
    if n == 1:
        return "1"
    
    prev = "1"
    for _ in range(2, n+1):
        current = []
        count = 1
        # Iterate through previous term to build current term
        for i in range(1, len(prev)):
            if prev[i] == prev[i-1]:
                count += 1
            else:
                current.append(str(count) + prev[i-1])
                count = 1
        # Add the last group of digits
        current.append(str(count) + prev[-1])
        prev = ''.join(current)
    
    return prev
 
# Example usage:
print(count_and_say(4))  # Output: "1211"
print(count_and_say(5))  # Output: "111221"

Time/Space Complexity#

  • Time Complexity: O(2ⁿ), as the length of the sequence grows exponentially (each term roughly doubles in length for large n).
  • Space Complexity: O(2ⁿ), to store the current term.

Edge Cases#

  • n=1 (base case, return "1").
  • n=0 (invalid input, return "" or handle with error).

Conclusion#

String problems are a cornerstone of programming interviews, testing your ability to manipulate data structures, handle edge cases, and optimize algorithms. By mastering these 10 problems, you’ll build a strong foundation in string manipulation and problem-solving—skills that will serve you well in technical interviews and real-world coding.

Practice these problems repeatedly, experiment with different approaches (e.g., optimizing time vs. space), and analyze edge cases to deepen your understanding.

References#

2025-10