String-Grundlagen
Anagramme, Palindrome und Häufigkeitszählung - das String-Werkzeug, plus warum Unveränderlichkeit StringBuilder in einer heißen Schleife zu deinem Freund macht.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.