String Essentials
Anagrams, palindromes, and frequency counting - the string toolkit, plus why immutability makes StringBuilder your friend in a hot loop.
On this page
Strings are just arrays of characters, so every array pattern applies - but they come with their own
toolkit and one big Java gotcha. This lesson covers the string problems that show up again and again:
anagrams, palindromes, and frequency counting, plus why StringBuilder matters in a hot loop.
Frequency counting is the string workhorse
A huge fraction of string problems reduce to counting characters. For lowercase ASCII, a
26-element int[] is faster and simpler than a HashMap; for arbitrary characters, use a map.
// are two strings anagrams? — O(n), O(1) space (fixed 26-letter alphabet)
boolean isAnagram(String a, String b) {
if (a.length() != b.length()) return false;
int[] count = new int[26];
for (int i = 0; i < a.length(); i++) {
count[a.charAt(i) - 'a']++; // add for a
count[b.charAt(i) - 'a']--; // remove for b
}
for (int c : count) if (c != 0) return false; // all must cancel
return true;
}The trick c - 'a' maps 'a'..'z' to indices 0..25 - a tiny bit of arithmetic that replaces a
hash map. Two strings are anagrams exactly when their character counts are identical, so incrementing
for one and decrementing for the other must leave all zeros.
Palindromes: two pointers again
Checking a palindrome is the converging two-pointer pattern from earlier - compare mirror positions from both ends inward, O(n) time and O(1) space, no reversed copy needed.
The immutability gotcha: use StringBuilder
Here's the trap that quietly makes string code O(n²): Java strings are immutable, so every +
or += builds a brand-new string by copying all the characters. Concatenating in a loop is
therefore O(n²):
// O(n^2): each += copies the whole accumulated string
String result = "";
for (String part : parts) result += part; // DON'T do this in a loop
// O(n): StringBuilder mutates one buffer (amortized, like ArrayList)
StringBuilder sb = new StringBuilder();
for (String part : parts) sb.append(part);
String result = sb.toString();StringBuilder keeps a single growable char buffer and appends in place (amortized O(1) per append,
by the same doubling logic as ArrayList). Reaching for it in any loop that builds a string is a
mark of someone who knows Java's performance model.
Know your String toolkit
A few methods solve most string problems: charAt(i), length(), substring(i, j),
toCharArray(), indexOf, split, and Character.isLetterOrDigit / toLowerCase for cleaning
input. For counting, prefer an int[26] for lowercase letters and a HashMap<Character, Integer>
for anything wider.
Immutable strings are like a document you can never edit - to add a word, you must recopy the entire
letter onto a fresh page with the word included. Do that once per word and a long letter costs a
mountain of recopying (O(n²)). A StringBuilder is a whiteboard instead: you just add to what's
already there, wiping and expanding as needed, so building the whole message is cheap. Same final
text, wildly different effort.
Given a list of words, group together the ones that are anagrams of each other (e.g. "eat," "tea," and "ate" in one group). Describe a key you could compute for each word so that anagrams share the same key, and which data structure collects the groups.
Why is building a string with += inside a loop O(n^2) in Java?
Key takeaways
- Strings are arrays of characters, so array patterns (two pointers, sliding window) apply directly.
- Frequency counting is the string workhorse: int[26] for lowercase letters, a HashMap for wider alphabets.
- Anagrams share identical character counts (or the same sorted-letter key); palindromes are a two-pointer check.
- The trick c - 'a' maps letters to 0..25 indices, replacing a hash map for lowercase input.
- Java strings are immutable: use StringBuilder in loops to avoid O(n^2) concatenation.