String Manipulation

At a glance

The instinct

A string is an array of char that happens to be immutable in Java. Most "string manipulation" questions are really careful index bookkeeping: skip what does not matter (spaces, punctuation, case), compare what does, and assemble a new string efficiently. The pattern is less about a clever idea and more about clean, bug-free traversal: knowing which index moves, when it stops, and how you build the result without accidentally going quadratic.

When you read a problem about characters, words, prefixes, palindromes or encoding, your default plan should be: convert to char[] if you need to mutate, walk with one or two indices, and collect output in a StringBuilder.

Recognise it

Not this pattern if...

• You need the longest/shortest substring satisfying a constraint: use Sliding Window.
• The question is about character frequencies, anagrams or "can be rearranged": use Hashing & Counting.
• You must count or find palindromic subsequences or edit distance: that is Dynamic Programming.
• You need fast repeated pattern matching (KMP, rolling hash): that is a dedicated string-matching algorithm.

Memory hack

Say it out loud in the interview:

1. "What is the character set and is case significant?" (ASCII lowercase means an int[26] or simple comparisons.)
2. "Which indices am I walking, and what makes each one move or stop?"
3. "I'll build output with a StringBuilder and convert once, so the whole thing stays O(n)."

How it works

Most problems use one of three skeletons:

1. Converging pointers (Valid Palindrome): i from the left, j from the right, each skipping characters that do not count, then comparing lowercase forms.
2. Chasing pointers (Is Subsequence): one pointer walks the long string every step; the other walks the short string only on a match. If the short pointer reaches the end, it is a subsequence.
3. Scan and rebuild (Reverse Words in a String, Zigzag Conversion, Encode and Decode Strings): read tokens or positions, then write them into a builder in a new order.

flowchart LR
  A[Input string] --> B{Need to mutate?}
  B -- yes --> C[toCharArray]
  B -- no --> D[charAt walk]
  C --> E[Move indices with clear stop rules]
  D --> E
  E --> F{Producing new text?}
  F -- yes --> G[Append to StringBuilder]
  F -- no --> H[Return boolean / index / count]
  G --> I[toString once]

For Encode and Decode Strings, a robust format is length#payload for each item: ["ab", "c#d"] becomes 2#ab3#c#d. While decoding, read digits up to #, then take exactly that many characters, so delimiters inside the payload never confuse you.

Java template

import java.util.ArrayList;
import java.util.List;

class StringToolkit {
    // Converging pointers with a skip rule (palindrome-style checks).
    static boolean symmetricCheck(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !counts(s.charAt(i))) i++;   // skip noise on the left
            while (i < j && !counts(s.charAt(j))) j--;   // skip noise on the right
            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
            i++; j--;
        }
        return true;
    }

    static boolean counts(char c) {
        return Character.isLetterOrDigit(c);              // problem-specific filter
    }

    // Scan tokens, then rebuild in a new order with one StringBuilder.
    static String rebuildWords(String s) {
        List<String> words = new ArrayList<>();
        int i = 0, n = s.length();
        while (i < n) {
            while (i < n && s.charAt(i) == ' ') i++;      // skip separators
            int start = i;
            while (i < n && s.charAt(i) != ' ') i++;      // consume one token
            if (start < i) words.add(s.substring(start, i));
        }
        StringBuilder sb = new StringBuilder();
        for (int k = words.size() - 1; k >= 0; k--) {     // problem-specific order
            if (sb.length() > 0) sb.append(' ');
            sb.append(words.get(k));
        }
        return sb.toString();
    }

    // Length-prefixed encoding: safe for any characters inside the payload.
    static String encode(List<String> items) {
        StringBuilder sb = new StringBuilder();
        for (String it : items) sb.append(it.length()).append('#').append(it);
        return sb.toString();
    }

    static List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (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;
    }
}

Complexity

• Index walks and two-pointer checks: O(n) time, O(1) extra space when you use charAt.
• Rebuilding with a StringBuilder: O(n) time and O(n) space for the output.
• Longest Common Prefix (vertical scan): O(S) where S is the total number of characters examined.
• toCharArray() costs O(n) space; that is fine unless the interviewer insists on constant memory.
• Repeated s = s + c inside a loop is O(n^2) because each concatenation copies the whole string.

Variations

• Palindrome checks: converging pointers with a filter. Valid Palindrome; expand-from-centre is the cousin for finding palindromic substrings.
• Subsequence matching: chasing pointers across two strings. Is Subsequence.
• Prefix comparison: vertical scan, or sort and compare only the first and last strings. Longest Common Prefix.
• Tokenise and reorder: split on separators manually and rebuild. Reverse Words in a String.
• Layout simulation: map each character to a row with a bouncing direction. Zigzag Conversion.
• Serialisation: length prefixes or escaping. Encode and Decode Strings.
• Interactive elimination: compare candidate words by matching positions and filter the pool after each guess. Guess the Word.

Common mistakes

• Using == to compare String objects instead of .equals(); == checks identity, not content.
• Off-by-one errors with substring(start, end), whose end index is exclusive.
• Forgetting the i < j guard inside the skip loops, which lets pointers cross or run out of bounds on strings like ".,".
• Splitting with s.split(" ") and getting empty tokens when there are multiple spaces; use trim() plus split("\\s+"), or scan manually.
• Choosing a delimiter for encoding (like a comma) that can also appear inside the data.

All practice problems

7 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.