String Problems & Sliding Window — Interview Questions

How to use this lesson

Most string questions reduce to a few patterns:

• a sliding window with a frequency map;
• hashing a canonical form;
• expanding around centres;
• careful parsing.

State what the character set is (ASCII, so a 128-element array, or Unicode, so a map), because it changes both space and speed.

Learn it in depth → Sliding Window Pattern

Q1. Longest substring without repeating characters.

Short answer: Use a sliding window, with the last index of each character. When a repeat appears inside the window, jump the left edge to last + 1. O(n) time, O(charset) space. (Practice)

int lengthOfLongestSubstring(String s) {
    int[] last = new int[128]; Arrays.fill(last, -1);
    int best = 0;
    for (int l = 0, r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        if (last[c] >= l) l = last[c] + 1;
        last[c] = r;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Q2. Group anagrams efficiently.

Short answer: Anagrams share a canonical key:

• sorted characters: O(k log k) per word;
• or, faster, a 26-count signature ("#1#0#2…"): O(k) per word.

Group them in HashMap<String, List<String>>. The total is O(n·k) with the counting key. (Practice)

List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String w : words) {
        int[] cnt = new int[26];
        for (char c : w.toCharArray()) cnt[c - 'a']++;
        groups.computeIfAbsent(Arrays.toString(cnt), k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}

Learn it in depth → String Hashing & Anagrams

Q3. Minimum window substring.

Short answer: Count the characters needed from t. Expand r until the window covers everything (missing == 0), then shrink l as far as possible while it stays valid, recording the best window. O(|s| + |t|). (Practice)

String minWindow(String s, String t) {
    int[] need = new int[128]; for (char c : t.toCharArray()) need[c]++;
    int missing = t.length(), bestL = 0, bestLen = Integer.MAX_VALUE;
    for (int l = 0, r = 0; r < s.length(); r++) {
        if (need[s.charAt(r)]-- > 0) missing--;
        while (missing == 0) {
            if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
            if (++need[s.charAt(l++)] > 0) missing++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
}

Q4. Longest palindromic substring (expand around the centre, and DP).

Short answer:

• Expand around each centre (2n−1 centres: every character, and every gap between characters): O(n²) time, O(1) space. It's the preferred answer.
• DP: dp[i][j] = s[i]==s[j] && (j-i < 3 || dp[i+1][j-1]), filled by increasing length. O(n²) time and O(n²) space.
• Manacher's algorithm achieves O(n), but it's rarely expected.

String longestPalindrome(String s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len = Math.max(expand(s, i, i), expand(s, i, i + 1));
        if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; }
    }
    return s.substring(start, end + 1);
}
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

Q5. Zigzag conversion.

Short answer: Simulate the zigzag with one StringBuilder per row: walk the characters, moving down the rows, then flip direction at the top and bottom rows. Then join the rows. O(n). Handle numRows == 1 separately (return the input).

String convert(String s, int rows) {
    if (rows == 1 || rows >= s.length()) return s;
    StringBuilder[] sb = new StringBuilder[rows];
    for (int i = 0; i < rows; i++) sb[i] = new StringBuilder();
    int row = 0, step = 1;
    for (char c : s.toCharArray()) {
        sb[row].append(c);
        if (row == 0) step = 1; else if (row == rows - 1) step = -1;
        row += step;
    }
    return String.join("", sb);
}

Q6. Compare version numbers.

Short answer: Split on "\\." (a regex, so the dot must be escaped). Compare the parts numerically (so "01" equals "1"), treating missing parts as 0 ("1.0" equals "1"). O(n + m).

int compareVersion(String v1, String v2) {
    String[] a = v1.split("\\."), b = v2.split("\\.");
    for (int i = 0; i < Math.max(a.length, b.length); i++) {
        int x = i < a.length ? Integer.parseInt(a[i]) : 0;
        int y = i < b.length ? Integer.parseInt(b[i]) : 0;
        if (x != y) return Integer.compare(x, y);
    }
    return 0;
}

Common trap: split(".") treats the dot as the regex "any character", so it returns an empty array.

Q7. Encode and decode a list of strings.

Short answer: Use length-prefix framing: len + '#' + str for each string. Decoding reads the digits up to #, then exactly len characters. It works for any content, including # and empty strings. Delimiter-only or escaping schemes are fragile. O(total length).

String encode(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s.length()).append('#').append(s);
    return sb.toString();
}
List<String> decode(String s) {
    List<String> out = new ArrayList<>();
    for (int i = 0; i < s.length(); ) {
        int hash = s.indexOf('#', i);
        int len = Integer.parseInt(s.substring(i, hash));
        out.add(s.substring(hash + 1, hash + 1 + len));
        i = hash + 1 + len;
    }
    return out;
}

Q8. Sliding window maximum.

Short answer: Use a monotonic deque of indices, with values decreasing from the front:

1. drop the front index if it has left the window;
2. pop from the back while the back value is at most the new value (those elements can never be a maximum again);
3. push the new index. The front is the window's maximum.

O(n): each index is pushed and popped at most once. (A heap would be O(n log n).)

int[] maxSlidingWindow(int[] a, int k) {
    int[] res = new int[a.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < a.length; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
        dq.offerLast(i);
        if (i >= k - 1) res[i - k + 1] = a[dq.peekFirst()];
    }
    return res;
}

Follow-up questions this topic invites — and their answers

Q: Why use StringBuilder instead of string concatenation in loops? A: Strings are immutable, so += in a loop creates a new string each time (O(n²) total copying). StringBuilder appends in amortised O(1).

Q: How would these solutions change for Unicode input? A: Replace the fixed 128-element arrays with a HashMap<Integer, Integer> over code points (s.codePoints()), because characters outside the Basic Multilingual Plane use two char values (surrogate pairs).

Q: When is a monotonic deque the right tool? A: For the maximum or minimum over a sliding window, and in DP optimisations where you need the best value among the last k states. It keeps the candidates in order and discards those dominated by newer elements.

Q: What's the time complexity of String.substring in modern Java? A: O(length of the substring). Since Java 7u6 it copies the characters (it no longer shares the backing array), so repeated substrings in loops have a real cost.