String Manipulation Basics

Description

Strings look like arrays of letters, but they differ in three ways that matter. They can't be changed in place. A Java char isn't always a whole character. And many string questions ("same letters?", "reads the same backwards?") are about counts and symmetry rather than positions. This skill covers the standard techniques, counting and two-pointer or center expansion, and the standard ways each one goes wrong on real text.

We'll go from simple to more technical:

1. The pattern: count characters (anagrams), and compare from both ends (palindromes).
2. A second flavor: expand around every center to find the longest palindrome.
3. Where these show up in production (search, deduplication, validation).
4. What breaks it: assumed alphabets, Unicode, building strings in loops, ==.

The approach

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;      // different lengths can never match
    int[] counts = new int[26];                      // lowercase a-z only
    for (int i = 0; i < s.length(); i++) {
        counts[s.charAt(i) - 'a']++;
        counts[t.charAt(i) - 'a']--;
    }
    for (int c : counts) if (c != 0) return false;
    return true;
}

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False                                 # different lengths can never match
    counts = [0] * 26                                # lowercase a-z only
    for a, b in zip(s, t):
        counts[ord(a) - ord("a")] += 1
        counts[ord(b) - ord("a")] -= 1
    return all(c == 0 for c in counts)

# for any alphabet: collections.Counter(s) == collections.Counter(t)

Two strings are anagrams exactly when every character appears the same number of times in both, so count instead of sorting: O(n) rather than O(n log n), with a 26-slot array in place of a HashMap. The index c - 'a' is the assumption to watch: 'A' - 'a' is -32, so an uppercase letter throws ArrayIndexOutOfBoundsException. For ASCII input use new int[128] indexed by the char itself; for arbitrary Unicode, count code points (s.codePoints()) in a map - counting chars in a HashMap<Character, Integer> counts the two halves of an emoji separately, and "🔥🤖" and "🔖🤥" then look like anagrams.

A second flavor: expand around the center

Palindromes are about symmetry. To check one string, move two pointers inward from the ends. To find the longest palindromic substring, grow outward from every possible center:

int longestPalindromeLength(String s) {
    int best = 0;
    for (int c = 0; c < s.length(); c++) {
        best = Math.max(best, expand(s, c, c));      // odd length: centered on a character
        best = Math.max(best, expand(s, c, c + 1));  // even length: centered on a gap
    }
    return best;
}

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;                                // the loop overshoots by one on each side
}

def longest_palindrome_length(s: str) -> int:
    best = 0
    for c in range(len(s)):
        best = max(best, expand(s, c, c))            # odd length: centered on a character
        best = max(best, expand(s, c, c + 1))        # even length: centered on a gap
    return best


def expand(s: str, lo: int, hi: int) -> int:
    while lo >= 0 and hi < len(s) and s[lo] == s[hi]:   # lo >= 0 matters: s[-1] is the last character
        lo -= 1
        hi += 1
    return hi - lo - 1                               # the loop overshoots by one on each side

There are 2n - 1 centers: n characters and n - 1 gaps between them. Using only character centers misses every even-length palindrome - on "zoom" it answers 1 instead of 2. Each expansion is O(n) in the worst case (a string of one repeated letter), so the total is O(n^2) time and O(1) space.

Where you'll see it

Comparing tag sets or keyword bags ("same words, any order") is the same frequency count over a bigger alphabet. Length limits are where code units bite: a 20-character username limit checked with length() rejects 11 emoji (22 chars), while a database column that counts characters would accept them - so decide which "character" a limit means and check it the same way everywhere.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does counts[c - 'a']++ crash on "Listen" and "Silent", and how do you fix it?

2. How many centers does expand-around-center try for a string of length n, and what goes wrong if you only use character centers?

3. Why is s = s + c inside a loop O(n^2), and what should you use instead?

Key takeaways

• Anagram = same character counts; a count array does it in O(n), but c - 'a' assumes lowercase a-z.
• A char is a UTF-16 unit: emoji take two. Count code points for arbitrary text.
• Find palindromes by expanding from all 2n - 1 centers - odd and even.
• Strings are immutable: build with StringBuilder.append, not + or insert(0, ...) in a loop.
• Compare strings with equals, never ==.