Autocoder

String interview questions with worked solutions

Last updated 2026-11-19

String questions look simple, but they hide the same traps every time: immutability, character sets, case, whitespace and the cost of building a result by repeated concatenation. Interviewers use them to see whether you can reason about an input you cannot index into freely or modify in place.

The problems below run from easy to hard. They cover palindromes, anagrams, parsing, expansion around a centre and stack-based decoding. For problems that slide a window over a string or match patterns, see sliding window questions and KMP string matching questions.

Problems10, easy to hard
LanguagesPython and Java
Key toolsTwo pointers, count arrays, expansion, stack

Questions to ask before coding

Ask what the alphabet is: lowercase English letters allow a 26-slot count array, while Unicode needs a map. Ask whether case and spaces matter, and whether the input can be empty or null.

In Java, strings are immutable, so build results with StringBuilder. In Python, collect parts in a list and join once rather than using += in a loop on large inputs.

Typical traps

Whitespace-only strings, leading or trailing spaces and repeated spaces break naive split logic. Integer parsing breaks on overflow and signs. Palindrome checks break on even length when you only expand from one centre.

String interview questions with worked solutions: questions with worked answers

  1. 1

    Check whether a string is a palindrome, ignoring case and non-alphanumeric characters.

    easy

    Use two pointers from the ends. Skip characters that are not letters or digits on each side, then compare lower-cased characters. Stop when the pointers meet. No cleaned copy is needed. Time O(n), space O(1).. Edge cases: empty string or only punctuation (true), mixed case, digits.

    python
    def is_palindrome(s):
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True
    java
    import java.util.*;
    
    class Solution {
        static boolean isPalindrome(String s) {
            int l = 0, r = s.length() - 1;
            while (l < r) {
                while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
                while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
                if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
                l++;
                r--;
            }
            return true;
        }
    }
  2. 2

    Are two strings anagrams of each other?

    easy

    If the lengths differ, return false. Otherwise keep a 26-slot count, adding one for each character of the first string and subtracting one for each of the second. All counts must end at zero. For Unicode input, use a map keyed by character instead of an array. Time O(n), space O(1) for a fixed alphabet.. Edge cases: different lengths, empty strings, uppercase letters if allowed.

    python
    def is_anagram(s, t):
        if len(s) != len(t):
            return False
        c = [0] * 26
        for a, b in zip(s, t):
            c[ord(a) - 97] += 1
            c[ord(b) - 97] -= 1
        return not any(c)
    java
    import java.util.*;
    
    class Solution {
        static boolean isAnagram(String s, String t) {
            if (s.length() != t.length()) return false;
            int[] c = new int[26];
            for (int i = 0; i < s.length(); i++) {
                c[s.charAt(i) - 'a']++;
                c[t.charAt(i) - 'a']--;
            }
            for (int x : c) if (x != 0) return false;
            return true;
        }
    }
  3. 3

    Find the index of the first non-repeating character.

    easy

    Count every character in one pass, then scan again in original order and return the first index whose count is one. Two passes are needed because uniqueness is only known after the whole string is read. Time O(n), space O(k) for k distinct characters.. Edge cases: no unique character (return -1), empty string.

    python
    from collections import Counter
    
    def first_unique(s):
        c = Counter(s)
        for i, ch in enumerate(s):
            if c[ch] == 1:
                return i
        return -1
    java
    import java.util.*;
    
    class Solution {
        static int firstUnique(String s) {
            int[] c = new int[65536];
            for (char ch : s.toCharArray()) c[ch]++;
            for (int i = 0; i < s.length(); i++) if (c[s.charAt(i)] == 1) return i;
            return -1;
        }
    }
  4. 4

    Check whether one string is a rotation of another.

    easy

    A rotation of s is always a substring of s + s. So the answer is true when the lengths match and t occurs inside s + s. For s = "abcde" and t = "cdeab", s + s = "abcdeabcde" contains t. Time O(n) with a linear-time search such as KMP, O(n^2) worst case with a naive search; space O(n).. Edge cases: different lengths, both empty (true), repeated patterns like "aa".

    python
    def is_rotation(s, t):
        return len(s) == len(t) and t in s + s
    java
    import java.util.*;
    
    class Solution {
        static boolean isRotation(String s, String t) {
            return s.length() == t.length() && (s + s).contains(t);
        }
    }
  5. 5

    Find the longest common prefix among an array of strings.

    medium

    Start with the first string as the prefix and shorten it until each other string starts with it. The prefix only ever shrinks, so one pass over the array is enough. The loop ends at the latest when the prefix is empty, since every string starts with "". Time O(total characters), space O(1) beyond the prefix.. Edge cases: empty array, one string, a string that is empty.

    python
    def longest_common_prefix(strs):
        if not strs:
            return ""
        p = strs[0]
        for s in strs[1:]:
            while not s.startswith(p):
                p = p[:-1]
        return p
    java
    import java.util.*;
    
    class Solution {
        static String longestCommonPrefix(String[] strs) {
            if (strs.length == 0) return "";
            String p = strs[0];
            for (int i = 1; i < strs.length; i++)
                while (!strs[i].startsWith(p)) p = p.substring(0, p.length() - 1);
            return p;
        }
    }
  6. 6

    Reverse the words in a sentence, collapsing extra spaces.

    medium

    Split on runs of whitespace, reverse the word list and join with single spaces. In Java, trim first so the split does not produce a leading empty token. The interview follow-up is doing it in place on a character array: reverse the whole array, then reverse each word. Time O(n), space O(n).. Edge cases: leading and trailing spaces, multiple spaces between words, empty or all-space input.

    python
    def reverse_words(s):
        return " ".join(reversed(s.split()))
    java
    import java.util.*;
    
    class Solution {
        static String reverseWords(String s) {
            String[] w = s.trim().split("\\s+");
            StringBuilder sb = new StringBuilder();
            for (int i = w.length - 1; i >= 0; i--) {
                sb.append(w[i]);
                if (i > 0) sb.append(' ');
            }
            return sb.toString();
        }
    }
  7. 7

    Implement atoi: convert a string to a 32-bit signed integer.

    medium

    Skip leading spaces, read an optional sign, then accumulate digits until a non-digit. Clamp on overflow before it happens: in Java check against MAX/10 and the last digit, in Python compare the running value with the limits. Anything after the digits is ignored. Time O(n), space O(1).. Edge cases: only spaces, a sign with no digits, values beyond 2^31 - 1 or below -2^31, leading zeroes.

    python
    def my_atoi(s):
        i, n, sign = 0, len(s), 1
        while i < n and s[i] == ' ':
            i += 1
        if i < n and s[i] in '+-':
            sign = -1 if s[i] == '-' else 1
            i += 1
        r = 0
        while i < n and '0' <= s[i] <= '9':
            r = r * 10 + (ord(s[i]) - 48)
            if sign * r > 2**31 - 1:
                return 2**31 - 1
            if sign * r < -2**31:
                return -2**31
            i += 1
        return sign * r
    java
    import java.util.*;
    
    class Solution {
        static int myAtoi(String s) {
            int i = 0, n = s.length(), sign = 1, r = 0;
            while (i < n && s.charAt(i) == ' ') i++;
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-'))
                sign = s.charAt(i++) == '-' ? -1 : 1;
            while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                int d = s.charAt(i++) - '0';
                if (r > Integer.MAX_VALUE / 10 || (r == Integer.MAX_VALUE / 10 && d > 7))
                    return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                r = r * 10 + d;
            }
            return sign * r;
        }
    }
  8. 8

    Find the longest palindromic substring.

    medium

    Every palindrome has a centre, either a character or a gap between two. Try all 2n-1 centres and expand outwards while the ends match, remembering the best range. Manacher gives O(n), but expansion is the answer most interviewers expect. For "babad" it returns "bab" or "aba". Time O(n^2), space O(1).. Edge cases: length 0 or 1, all identical characters, even-length palindromes such as "abba".

    python
    def longest_palindrome(s):
        best = (0, 0)
        for c in range(len(s)):
            for l, r in ((c, c), (c, c + 1)):
                while l >= 0 and r < len(s) and s[l] == s[r]:
                    l -= 1
                    r += 1
                if r - l - 1 > best[1] - best[0]:
                    best = (l + 1, r)
        return s[best[0]:best[1]]
    java
    import java.util.*;
    
    class Solution {
        static String longestPalindrome(String s) {
            int start = 0, len = 0;
            for (int c = 0; c < s.length(); c++) {
                for (int k = 0; k < 2; k++) {
                    int l = c, r = c + k;
                    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
                    if (r - l - 1 > len) { len = r - l - 1; start = l + 1; }
                }
            }
            return s.substring(start, start + len);
        }
    }
  9. 9

    Multiply two non-negative numbers given as strings, without converting them to integers.

    hard

    Digit i of the first and digit j of the second contribute to positions i+j and i+j+1 of a result array of length m+n. Multiply from the right, add the existing value at i+j+1, store the units digit there and add the carry to i+j. Strip leading zeroes at the end. Time O(m*n), space O(m+n).. Edge cases: either operand "0", unequal lengths, a result with a leading zero slot.

    python
    def multiply(a, b):
        if a == "0" or b == "0":
            return "0"
        res = [0] * (len(a) + len(b))
        for i in range(len(a) - 1, -1, -1):
            for j in range(len(b) - 1, -1, -1):
                s = int(a[i]) * int(b[j]) + res[i + j + 1]
                res[i + j + 1] = s % 10
                res[i + j] += s // 10
        return "".join(map(str, res)).lstrip("0")
    java
    import java.util.*;
    
    class Solution {
        static String multiply(String a, String b) {
            if (a.equals("0") || b.equals("0")) return "0";
            int[] res = new int[a.length() + b.length()];
            for (int i = a.length() - 1; i >= 0; i--) {
                for (int j = b.length() - 1; j >= 0; j--) {
                    int s = (a.charAt(i) - '0') * (b.charAt(j) - '0') + res[i + j + 1];
                    res[i + j + 1] = s % 10;
                    res[i + j] += s / 10;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int d : res) if (!(sb.length() == 0 && d == 0)) sb.append(d);
            return sb.toString();
        }
    }
  10. 10

    Decode a string such as 3[a2[c]] into accaccacc.

    hard

    Use a stack. Keep the current string and the pending repeat count. On "[", push the current string and count and reset. On "]", pop them and set current to previous + current repeated count times. Digits may have several places, so build the number as k = k*10 + digit. Time O(size of output), space O(depth of nesting).. Edge cases: multi-digit counts like 12[a], nested brackets, plain letters with no brackets.

    python
    def decode(s):
        st, cur, k = [], "", 0
        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == "[":
                st.append((cur, k))
                cur, k = "", 0
            elif ch == "]":
                prev, n = st.pop()
                cur = prev + cur * n
            else:
                cur += ch
        return cur
    java
    import java.util.*;
    
    class Solution {
        static String decode(String s) {
            Deque<StringBuilder> strs = new ArrayDeque<>();
            Deque<Integer> counts = new ArrayDeque<>();
            StringBuilder cur = new StringBuilder();
            int k = 0;
            for (char ch : s.toCharArray()) {
                if (Character.isDigit(ch)) k = k * 10 + (ch - '0');
                else if (ch == '[') { strs.push(cur); counts.push(k); cur = new StringBuilder(); k = 0; }
                else if (ch == ']') {
                    StringBuilder prev = strs.pop();
                    int n = counts.pop();
                    for (int i = 0; i < n; i++) prev.append(cur);
                    cur = prev;
                } else cur.append(ch);
            }
            return cur.toString();
        }
    }

Frequently asked questions

Which string problems come up most in coding rounds?

Palindromes, anagrams, longest substring variants, parsing problems such as atoi, and decoding with a stack. Practise one of each family rather than ten of the same kind.

Why avoid += on strings in a loop in Java?

Strings are immutable, so each concatenation copies the whole string, making the loop O(n^2). StringBuilder appends in amortised constant time.

When do I use a count array instead of a HashMap?

When the alphabet is small and fixed, such as lowercase letters. It is faster and uses constant space. Use a map for Unicode or arbitrary tokens.

How do I handle Unicode in these problems?

In Java, a char is a UTF-16 unit, so emoji take two. Most interview questions assume ASCII or lowercase letters; state that assumption aloud before you code.

Where do I practise anagram grouping and frequency counting?

See hashing interview questions, which cover group anagrams and ransom-note style problems in depth.

Related guides

More in DSA Interview Questions

See all in this section