Strings in Data Structures

Written and maintained by the JBattle team · Last updated 5 September 2026

A string is an array of characters with one extra rule in most languages: you cannot change it. That rule explains why a builder exists, why concatenating in a loop is a performance trap, and why so many string questions are really array questions in disguise.

▶ Start with Immutability & cost

Lessons: 3
Read time: 24 m
Practice problems: 13
Track: Data Structures & Algorithms

Lessons in order

01Immutability & costWhy strings are immutable, why building one in a loop is O(n squared), and how StringBuilder, join and rope-style buffers fix it.7 min 02Palindromes & anagramsSolve palindrome checks with two pointers and anagram checks with frequency counting, including the expand-around-centre technique.8 min 03Pattern matchingHow substring search works: the naive O(n x m) scan, why it repeats work, and how the KMP prefix table brings it down to O(n + m).9 min

What you will be able to do

Immutability buys safe sharing, cached hashes and thread safety.
Palindrome checks are two pointers converging from both ends: O(n) time, O(1) space.
Naive search is O(n x m) because it rechecks characters it already matched.

Quiz yourself on Strings

Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.

⚡ Start the Strings quiz

Frequently asked questions

Why are strings immutable in Java and Python?

Immutability lets strings be shared freely between references and threads without defensive copying, allows the hash code to be cached so strings work well as map keys, and enables interning of identical literals.

Why is string concatenation in a loop O(n squared)?

Each concatenation allocates a new string and copies everything accumulated so far. Copy lengths 1, 2, 3 ... n sum to n(n+1)/2, which is quadratic.

What is the difference between String, StringBuilder and StringBuffer?

String is immutable. StringBuilder is a mutable buffer designed for building strings efficiently in a single thread. StringBuffer is the same idea with synchronised methods, which makes it thread-safe but slower.

How do you check if a string is a palindrome?

Put one pointer at each end and walk them inwards, comparing characters and skipping anything you were told to ignore. If every compared pair matches, it is a palindrome. O(n) time, O(1) space.

What is the best way to check if two strings are anagrams?

Count character frequencies in one pass, incrementing for the first string and decrementing for the second, then check that every count ended at zero. That is O(n), against O(n log n) for sorting both.

How do you find the longest palindromic substring?

Expand around each of the 2n-1 possible centres, remembering the longest match. That is O(n squared) with O(1) space; Manacher's algorithm reduces it to O(n).