String Manipulation Techniques: Reversal, Palindromes, and Anagrams
String manipulation in Python and Java: why immutability makes naive concatenation O(n^2), safe ways to reverse, and how to check palindromes and anagrams in linear time.
O(n^2); respect it and you build once with "".join or StringBuilder. Reversal, palindrome checks, and anagram checks then become linear scans with two pointers or character counts. Learn the immutability rule first, because every other technique follows from it.
An export job works fine in testing with a few hundred rows. In production it handles tens of thousands of rows and becomes the slowest step in the pipeline. The culprit is one line: line += field + "," inside a loop. Each pass copies everything built so far, so the work grows with the square of the output length.
String manipulation techniques are the small set of moves you use to build, reverse, compare, and count characters in text efficiently. Interviewers use them as warm-ups, and production code uses them everywhere from CSV writers to search normalization. The same handful of ideas covers reversal, palindromes, and anagrams.
The code targets Python 3.12 and Java 21. You need loops, functions, and Big-O notation, which describes how running time grows with input size n. A string here is a sequence of characters stored like an array: indexed from 0, with constant-time access to any position.
My position: treat a string as an array you are not allowed to edit. When you need to edit, convert to a mutable buffer, do the work, and convert back once. That one habit prevents the most common string performance bug in both languages.
How to recognize when you need these techniques
String problems announce themselves through their wording. Watch for these signals:
- “Build”, “join”, “format”, or “serialize”. You are producing output from many pieces, so the concatenation strategy matters.
- “Reverse” or “read backward”. You need reversal of characters, words, or a sub-range.
- “Reads the same forward and backward”. That is a palindrome check, and two pointers solve it in
O(1)extra space. - “Same letters in a different order” or “rearrange”. That is an anagram check, solved by sorting or by counting characters.
- “Ignore case, spaces, and punctuation”. You need normalization or skip logic, and the edge cases live there.
- Input limits near 10^5 characters. Any quadratic copy pattern will time out, so build strings in linear time.
Why immutability changes every string algorithm
The Python standard types documentation describes strings as immutable sequences of Unicode code points. The Java String documentation says strings are constant and cannot change after creation. Immutability makes strings safe to share between threads and safe to use as dictionary keys. It also means you cannot change one character without making a new string.
So s += "x" never edits s. It allocates a new string, copies all of s, copies "x", and rebinds the name. Inside a loop, that copying adds up fast:
naive concatenation: every step copies the whole result so far
step 1: s = "a" [a] copies 1
step 2: s = s + "b" [a|b] copies 2
step 3: s = s + "c" [a|b|c] copies 3
step 4: s = s + "d" [a|b|c|d] copies 4
total = 1 + 2 + ... + n = n(n+1)/2
builder: append into a growable buffer, copy once at the end
[a| | | ] -> [a|b| | ] -> [a|b|c| ] -> [a|b|c|d] -> toString() / join: copies n
For 100,000 one-character pieces, the naive total is about five billion character copies. The builder’s buffer grows geometrically, the same way a dynamic array does, so appends cost amortized O(1) each. The guide to arrays: contiguous memory and shifting costs explains why geometric growth keeps the total linear.
The wrong and the right way to build a string
The wrong version, in Java:
String csv = "";
for (String field : fields) {
csv += field + ","; // builds a brand-new String holding everything so far
}
The right version:
StringBuilder csv = new StringBuilder();
for (String field : fields) {
csv.append(field).append(','); // appends into a growable buffer
}
String result = csv.toString(); // one final copy
With 50,000 fields, the wrong version copies a growing string 50,000 times. The right version appends into one buffer and copies once at the end. The StringBuilder documentation describes it as a mutable sequence of characters, which is exactly what the loop needs. In Python, the equivalent is collecting pieces in a list and calling ",".join(pieces), or writing to io.StringIO. The standard types documentation recommends both for linear-time building.
The myth: “the compiler or interpreter fixes this for me”
Half of this myth is true, which is what makes it dangerous. The Java String documentation notes that javac may compile + using StringBuilder or StringConcatFactory, depending on the JDK version. That optimizes a single expression. It cannot stop a loop from producing a new, longer string on every pass.
CPython goes further. Its 3.12 bytecode interpreter source has a specialization for s += t on a local variable. When nothing else references s, it extends the string in place. That is why a quick benchmark of += in a function often looks linear. The original insight here is how fragile that is. Change the target from a local variable to an attribute, or prepend instead of append, and the same loop turns quadratic. You can measure it yourself:
import timeit
class Report:
def __init__(self) -> None:
self.text = ""
def plus_equals_local(parts: list[str]) -> str:
s = ""
for p in parts:
s += p # CPython may extend s in place here
return s
def plus_equals_attribute(parts: list[str]) -> str:
report = Report()
for p in parts:
report.text += p # same line, but the target is an attribute
return report.text
def prepend(parts: list[str]) -> str:
s = ""
for p in parts:
s = p + s # always builds a new string
return s
def join(parts: list[str]) -> str:
return "".join(parts)
if __name__ == "__main__":
funcs = (plus_equals_local, plus_equals_attribute, prepend, join)
sample = ["a", "b", "c"]
assert all(f(sample) == "abc" for f in funcs if f is not prepend)
assert prepend(sample) == "cba"
for n in (20_000, 40_000, 80_000):
parts = ["x"] * n
row = [f"{f.__name__}={timeit.timeit(lambda: f(parts), number=3):.4f}s" for f in funcs]
print(f"n={n:>6} " + " ".join(row))
Run it and compare how each column grows as n doubles. A linear column roughly doubles. A quadratic column roughly quadruples. On CPython 3.12, the local += and join columns stay close to linear, while the attribute and prepend columns grow quadratically. The lesson is simple: write join on purpose rather than relying on an optimization that a refactor can silently remove.
Core string manipulation techniques in Python and Java
The program below implements five building blocks: reversing a string, reversing a character buffer in place, reversing word order, checking a palindrome, and checking an anagram two ways. Its tests cover normal inputs, empty and single-character strings, duplicates, and the Unicode edge case covered earlier.
In Python:
import unicodedata
from collections import Counter
def reverse_string(s: str) -> str:
return s[::-1] # new string, O(n) time and space
def reverse_in_place(chars: list[str]) -> None:
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
def reverse_words(sentence: str) -> str:
return " ".join(reversed(sentence.split())) # split() drops extra spaces
def is_palindrome(s: str) -> bool:
"""Ignore case and anything that is not a letter or digit."""
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].casefold() != s[right].casefold():
return False
else:
left += 1
right -= 1
return True
def is_anagram_sorted(a: str, b: str) -> bool:
return len(a) == len(b) and sorted(a) == sorted(b)
def is_anagram_counting(a: str, b: str) -> bool:
if len(a) != len(b):
return False
counts: dict[str, int] = {}
for ch in a:
counts[ch] = counts.get(ch, 0) + 1
for ch in b:
remaining = counts.get(ch, 0) - 1
if remaining < 0: # b has a character a ran out of
return False
counts[ch] = remaining
return True
def build_line(fields: list[str]) -> str:
return ",".join(fields) # one pass, one final string
if __name__ == "__main__":
# reversal: normal, empty, single, duplicates
assert reverse_string("stressed") == "desserts"
assert reverse_string("") == "" and reverse_string("x") == "x"
chars = list("noon!")
reverse_in_place(chars)
assert "".join(chars) == "!noon"
assert reverse_words(" the sky is blue ") == "blue is sky the"
assert reverse_words("") == ""
# palindromes: punctuation, case, empty, single, even and odd length
assert is_palindrome("Taco cat!")
assert is_palindrome("Was it a car or a cat I saw?")
assert not is_palindrome("palindrome")
assert is_palindrome("") and is_palindrome("a") and is_palindrome("!!")
assert is_palindrome("abba") and not is_palindrome("abca")
# anagrams: both methods must agree, including duplicates
cases = [("listen", "silent", True), ("aabb", "abab", True),
("aab", "abb", False), ("", "", True), ("a", "ab", False)]
for a, b, expected in cases:
assert is_anagram_sorted(a, b) == expected
assert is_anagram_counting(a, b) == expected
assert (Counter(a) == Counter(b)) == expected
assert build_line(["id", "name", "score"]) == "id,name,score"
assert build_line([]) == ""
# the edge case: code points are not what a reader sees as characters
decomposed = "cafe\u0301" # "e" followed by a combining accent
assert len(decomposed) == 5
assert reverse_string(decomposed)[0] == "\u0301" # accent now leads
composed = unicodedata.normalize("NFC", decomposed)
assert len(composed) == 4 and reverse_string(composed) == "\u00e9fac"
flag_india = "\U0001F1EE\U0001F1F3" # two regional indicator code points
assert reverse_string(flag_india) == "\U0001F1F3\U0001F1EE" # a different flag
print("all tests passed")
The same techniques in Java:
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class StringTechniques {
static String reverse(String s) {
return new StringBuilder(s).reverse().toString(); // keeps surrogate pairs intact
}
static void reverseInPlace(char[] chars) {
int left = 0;
int right = chars.length - 1;
while (left < right) {
char tmp = chars[left];
chars[left] = chars[right];
chars[right] = tmp;
left++;
right--;
}
}
static String reverseWords(String sentence) {
String trimmed = sentence.trim();
if (trimmed.isEmpty()) {
return "";
}
String[] words = trimmed.split("\\s+");
StringBuilder out = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
out.append(words[i]);
if (i > 0) {
out.append(' ');
}
}
return out.toString();
}
static boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
char a = s.charAt(left);
char b = s.charAt(right);
if (!Character.isLetterOrDigit(a)) {
left++;
} else if (!Character.isLetterOrDigit(b)) {
right--;
} else if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
return false;
} else {
left++;
right--;
}
}
return true;
}
static boolean isAnagramSorted(String a, String b) {
if (a.length() != b.length()) {
return false;
}
char[] x = a.toCharArray();
char[] y = b.toCharArray();
Arrays.sort(x);
Arrays.sort(y);
return Arrays.equals(x, y);
}
static boolean isAnagramCounting(String a, String b) {
if (a.length() != b.length()) {
return false;
}
Map<Character, Integer> counts = new HashMap<>();
for (char ch : a.toCharArray()) {
counts.merge(ch, 1, Integer::sum);
}
for (char ch : b.toCharArray()) {
int remaining = counts.getOrDefault(ch, 0) - 1;
if (remaining < 0) { // b has a character a ran out of
return false;
}
counts.put(ch, remaining);
}
return true;
}
static String buildLine(List<String> fields) {
StringBuilder line = new StringBuilder();
for (int i = 0; i < fields.size(); i++) {
if (i > 0) {
line.append(',');
}
line.append(fields.get(i));
}
return line.toString();
}
static void check(boolean condition, String message) {
if (!condition) {
throw new AssertionError(message);
}
}
public static void main(String[] args) {
// reversal: normal, empty, single, duplicates
check(reverse("stressed").equals("desserts"), "reverse");
check(reverse("").isEmpty() && reverse("x").equals("x"), "reverse small");
char[] chars = "noon!".toCharArray();
reverseInPlace(chars);
check(new String(chars).equals("!noon"), "reverseInPlace");
check(reverseWords(" the sky is blue ").equals("blue is sky the"), "reverseWords");
check(reverseWords("").isEmpty(), "reverseWords empty");
// palindromes
check(isPalindrome("Taco cat!"), "taco cat");
check(isPalindrome("Was it a car or a cat I saw?"), "car or cat");
check(!isPalindrome("palindrome"), "not palindrome");
check(isPalindrome("") && isPalindrome("a") && isPalindrome("!!"), "tiny");
check(isPalindrome("abba") && !isPalindrome("abca"), "even length");
// anagrams: both methods agree, including duplicates
String[][] cases = {{"listen", "silent", "true"}, {"aabb", "abab", "true"},
{"aab", "abb", "false"}, {"", "", "true"}, {"a", "ab", "false"}};
for (String[] c : cases) {
boolean expected = Boolean.parseBoolean(c[2]);
check(isAnagramSorted(c[0], c[1]) == expected, "sorted " + c[0]);
check(isAnagramCounting(c[0], c[1]) == expected, "counting " + c[0]);
}
check(buildLine(List.of("id", "name", "score")).equals("id,name,score"), "buildLine");
check(buildLine(List.of()).isEmpty(), "buildLine empty");
// the edge case: one emoji is two char values in Java
String smile = "a\uD83D\uDE00"; // "a" followed by U+1F600
check(smile.length() == 3 && smile.codePointCount(0, smile.length()) == 2, "lengths");
check(reverse(smile).equals("\uD83D\uDE00a"), "StringBuilder keeps the pair");
char[] raw = smile.toCharArray();
reverseInPlace(raw);
check(Character.isLowSurrogate(raw[0]), "manual swap splits the pair");
System.out.println("PASS");
}
}
Note the two reversal styles. s[::-1] and StringBuilder.reverse() return new strings in O(n) time and O(n) space. The in-place version works on a list or char[], swaps from both ends, and uses O(1) extra space. That in-place swap is the version interviewers ask for when they say “you may not allocate another string.”
Palindrome checks with two pointers
A palindrome reads the same in both directions. The easy check is cleaned == cleaned[::-1], which costs O(n) time and O(n) extra space for the cleaned copy and its reverse. The two-pointer version gets the space down to O(1).
Place left at the start and right at the end. Skip any character that is not a letter or digit. Compare the rest case-insensitively and move both pointers inward. The invariant: every pair outside the window [left, right] has already matched. When the pointers meet or cross, the whole string has matched.
Here is a dry run of is_palindrome("Taco cat!"), with indexes 0 to 8:
| Step | left | s[left] | right | s[right] | Action |
|---|---|---|---|---|---|
| 1 | 0 | T | 8 | ! | Right is not alphanumeric, move right to 7 |
| 2 | 0 | T | 7 | t | Match ignoring case, move both |
| 3 | 1 | a | 6 | a | Match, move both |
| 4 | 2 | c | 5 | c | Match, move both |
| 5 | 3 | o | 4 | (space) | Right is not alphanumeric, move right to 3 |
| 6 | 3 | o | 3 | o | Pointers meet, return True |
Each step moves at least one pointer, so the loop runs at most n times. The same opposite-direction movement solves sorted pair sums and many container problems.
Anagram checks: sorting vs counting
Two strings are anagrams when they contain the same characters with the same multiplicities. Start with a length check, because it rejects most non-anagrams for free. Then pick one of two methods.
Sorting puts both strings in a canonical order and compares them. It costs O(n log n) time and O(n) space for the sorted copies. It shines when you need a canonical key, such as grouping many words by their sorted letters.
Counting tallies each character of the first string, then decrements for the second. If a count would drop below zero, the strings differ. It costs O(n) time and O(k) space, where k is the number of distinct characters. In Python, Counter(a) == Counter(b) does it in one line. When the input is guaranteed to be lowercase ASCII, an int[26] indexed by ch - 'a' is faster still.
Complexity of common string operations
| Operation | Time | Extra space | Notes |
|---|---|---|---|
| Read character at index | O(1) worst |
O(1) |
Java indexes UTF-16 code units |
| Concatenate two strings | O(n + m) worst |
O(n + m) |
Always builds a new string |
Repeated += in a loop |
O(L^2) worst |
O(L) |
L is the final length |
join / StringBuilder |
O(L) total, amortized |
O(L) |
The default way to build |
| Reverse to a new string | O(n) worst |
O(n) |
s[::-1], reverse() |
| Reverse a buffer in place | O(n) worst |
O(1) |
Two pointers on a list or array |
| Palindrome, two pointers | O(n) worst |
O(1) |
Skips non-alphanumerics |
| Anagram by sorting | O(n log n) worst |
O(n) |
Gives a canonical key |
| Anagram by counting | O(n) average |
O(k) |
Hash map counts are average case; a fixed array is worst case O(n) |
Unicode: when a character is not a character
Python indexes strings by Unicode code points, while Java indexes UTF-16 code units, so an emoji has length 1 in Python and 2 in Java. A hand-written Java swap loop splits that pair into invalid halves, although StringBuilder.reverse() keeps surrogate pairs together, as its documentation states. Neither language reverses what a reader sees as one character. An accented letter can be a base letter plus a combining mark, and a country flag is two code points. Normalizing to NFC with unicodedata.normalize or java.text.Normalizer fixes accents, but not flags or emoji sequences, which need a grapheme-aware library.
Where this shows up in real systems
- CPython’s interpreter loop. CPython 3.12 contains a dedicated in-place path for
s += ton local variables. Its existence shows how common the quadratic concatenation mistake is in real Python code. - The javac compiler. The Java String documentation states that javac may implement
+withStringBuilderorStringConcatFactorydepending on the JDK version. That improves single expressions, but loops still need an explicit builder. - Java’s StringBuilder.reverse. The JDK treats surrogate pairs as single characters during reversal. That design choice exists because naive char reversal corrupts text outside the Basic Multilingual Plane.
- Python’s buffered text building. The standard library points developers to
str.joinandio.StringIOfor building text in linear time, which is how you should write report and log builders.
How to explain it in an interview
Take Valid Palindrome as the example, since it is the most common warm-up. Start by asking clarifying questions. Does case matter? Should punctuation be ignored? Is an empty string a palindrome? The answer to the last one is usually yes.
Then walk through this order:
- Brute force. Build a cleaned lowercase copy and compare it with its reverse. That is
O(n)time andO(n)space. - Bottleneck. The extra copies are the only waste.
- Insight. Compare from both ends and skip ignored characters in place.
- Optimized solution. Two pointers with
O(1)extra space. - Edge cases. Empty string, all punctuation, one character, mixed case, and non-ASCII letters.
Common follow-ups include “allow one deletion,” “make it work on a stream,” and “what changes for Unicode.” A weak answer writes s == s[::-1] and stops. A strong answer names the space cost, offers two pointers, and mentions that Java’s char is a UTF-16 code unit, not a full character.
A decision framework for string problems
- Are you building output from many pieces? Collect the pieces and call
join, or useStringBuilder. Never grow a string with+in a loop. - Must you edit characters? Convert to a
listorchar[], edit, and convert back once. - Is it a symmetric comparison? Use two pointers from both ends with skip rules.
- Is it about the same letters in any order? Count characters for a yes or no answer, and sort when you need a grouping key.
- Is the alphabet small and fixed? Use an
int[26]orint[128]array instead of a hash map. - Is the text user-facing? Normalize first, and use a grapheme-aware library if reversal or truncation must respect what readers see.
When not to use these string techniques
- Do not sort to compare long strings with a small alphabet. Counting is linear, while sorting adds a
log nfactor and allocates copies. Sort only when you need a canonical key. - Do not reverse digits through string conversion when overflow rules matter. For problems like reversing a 32-bit integer, use arithmetic with explicit bounds checks instead.
- Do not hand-roll substring search for production text. Use the built-in
findorindexOf; specialized algorithms such as KMP matter only for unusual worst-case inputs.
A pattern I have seen in code reviews more than once: a CSV or log builder that uses += inside a loop in Java. It passes unit tests with a handful of rows, so nobody notices. It only shows up later, as a slow endpoint, once real exports grow to many thousands of rows. The fix is always the same three-line change to StringBuilder, and a review rule that flags += on strings inside loops.
Common mistakes
- Concatenating in a loop. It is quadratic in the output length. A 100,000-piece build exposes it as a timeout.
- Comparing strings with
==in Java. It compares references, not contents. Literals often pass because they are interned, while a string built at runtime fails. Useequals. - Skipping the length check in an anagram test. A counting loop over only the first string can wrongly accept
"a"and"ab". - Indexing
int[26]with uppercase or punctuation.'A' - 'a'is negative, which throwsArrayIndexOutOfBoundsException. Normalize case or use a larger table. - Splitting on a single space.
split(" ")keeps empty strings between repeated spaces. Usesplit()in Python ortrim().split("\\s+")in Java. - Reversing chars that form surrogate pairs. A manual swap loop in Java breaks emoji into invalid halves. Use
StringBuilder.reverse()or work with code points.
Practice problems
These problems drill the core string manipulation techniques in rising order of difficulty. Restate each one in your own words before you code it.
| Problem | Difficulty | The twist |
|---|---|---|
| Reverse String | Easy | Swap in place on a character array with O(1) extra space |
| Valid Palindrome | Easy | Skip non-alphanumerics and ignore case while moving two pointers |
| Valid Anagram | Easy | Count characters instead of sorting |
| Valid Palindrome II | Easy | On the first mismatch, try skipping either side once |
| Reverse Words in a String | Medium | Collapse repeated spaces, then reverse the word order |
| Group Anagrams | Medium | Use sorted letters or a count tuple as a hash key |
| Find All Anagrams in a String | Medium | Slide a window of fixed length and update counts incrementally |
| Longest Palindromic Substring | Medium | Expand around each center, including the gaps between characters |
The anagram-in-a-window problems lead naturally to fixed-size sliding windows over character counts. More DSA topics are on the DSA hub.
Key takeaways
- Strings are immutable in Python and Java, so every edit creates a new string.
- Build text with
join,io.StringIO, orStringBuilder, never with+in a loop. - Do not trust CPython’s in-place
+=optimization; it vanishes for attributes and prepends. - Reverse in place with two pointers on a mutable buffer when space is limited.
- Check palindromes with two pointers and skip rules in
O(1)extra space. - Check anagrams by counting for speed, and by sorting when you need a group key.
- Remember that Java
charvalues are UTF-16 code units, and neither language reverses what readers see as characters.
Frequently Asked Questions
Why are strings immutable in Python and Java?
Immutable strings can be shared safely between variables and threads, and their hash values never change, so they work as dictionary and map keys. The cost is that every modification creates a new string. Use a list with join or a StringBuilder when you need many edits.
Is string concatenation in a loop slow in Python?
It can be. CPython sometimes extends a local string in place, which hides the cost, but that is an implementation detail and it disappears for attributes and prepends. Collecting pieces in a list and calling join is reliably linear.
How do you reverse a string in Java?
Use new StringBuilder(s).reverse().toString(), which runs in linear time and keeps surrogate pairs such as emoji intact. A manual swap loop over a char array also works for plain ASCII text. Strings themselves cannot be reversed in place because they are immutable.
What is the fastest way to check if two strings are anagrams?
Compare lengths first, then count characters with a hash map or a fixed array for small alphabets. Counting runs in linear time, while sorting both strings costs O(n log n). Sorting is still useful when you need a canonical key for grouping.
Build strings once, compare them in place
Every one of these string manipulation techniques follows from immutability. Building text is cheap only when you append into a buffer and convert once. Comparing text is cheap when you walk it with pointers or counts instead of making copies.
Rule of thumb: if a loop body contains += on a string, rewrite it before anyone measures it.
Originally posted on 22 November 2026 and post last modified on 22 November 2026