Strings: Characters, Immutability, and Efficient Manipulation

Words are the data humans care about most: names, messages, searches, log lines. So it is no surprise that string problems are everywhere in interviews.

The good news is that a string is, to a first approximation, an array of characters. Almost everything you learned in the arrays article carries over. The bad news is that Java's String has some special rules, and ignoring them leads to slow code and strange bugs. This article covers both.

• How characters map to numbers, and the arithmetic tricks that follow.
• How to compare strings correctly.
• What immutability means, and when StringBuilder helps.
• How to solve palindrome, anagram and compression problems.
• What Java's length() really counts, and where Unicode surprises you.

In Java, a char is a 16-bit number that represents a character. The letters, digits and symbols you type on an English keyboard have codes between 0 and 127 (the ASCII range). The ones you need to remember are the runs:

Each run is consecutive, so subtracting the first character of a run gives a position within it. 'e' - 'a' is 4, and '7' - '0' is 7. Adding goes the other way: (char) ('a' + 4) is 'e'.

The Character class has methods so you do not need to remember ranges:

// File: Main.javapublic class Main {    public static void main(String[] args) {        System.out.println((int) 'A' + " " + (int) 'a' + " " + (int) '0');        System.out.println(Character.isLetter('x') + " " + Character.isDigit('7') + " " + Character.isLetterOrDigit('_'));        System.out.println(Character.toUpperCase('q') + " " + Character.getNumericValue('8'));        String a = "apple";        String b = "Apple";        System.out.println(a.equals(b) + " " + a.equalsIgnoreCase(b));        System.out.println(a.compareTo("banana") + " " + a.compareTo("apple") + " " + "b".compareTo("a"));        System.out.println(b.compareTo(a));    }}

65 97 48true true falseQ 8false true-1 0 1-32

About the comparisons:

• equals checks that two strings have the same characters. equalsIgnoreCase ignores case. Neither uses ==.
• compareTo returns a negative number, zero or a positive number. It compares character by character, and at the first difference returns the difference of the two character codes. This is lexicographic (dictionary-like) order based on character codes. That is why "Apple" comes before "apple": upper-case codes are smaller than lower-case codes.
• Do not rely on the exact value of a non-zero result, only on its sign.

A String in Java is immutable: once created, its characters can never change. Methods such as toUpperCase, substring and replace do not modify the string they are called on. They return a new string.

That has two consequences:

1. Safety. You can share a string freely without worrying that someone else will change it.
2. Cost. Any "change" builds a whole new string, which means copying characters.

The cost is invisible in one operation and enormous in a loop. Consider building a string of n characters by adding one character at a time with +=. Adding the 1st character copies 0 old characters, adding the 2nd copies 1, adding the 3rd copies 2, and so on. In total that is 0 + 1 + 2 + ... + (n - 1), which is n × (n - 1) / 2 copies, so O(n^2).

A StringBuilder is a mutable buffer. It keeps a growable array of characters inside and appends to it directly, with the same amortised O(1) cost per character that ArrayList has.

// File: Main.javapublic class Main {    public static void main(String[] args) {        int n = 1000;        String result = "";        long copiedByConcat = 0;        for (int i = 0; i < n; i++) {            copiedByConcat += result.length();   // the old characters are copied into a new string            result += 'x';        }        StringBuilder builder = new StringBuilder();        for (int i = 0; i < n; i++) {            builder.append('x');        }        System.out.println(result.equals(builder.toString()));        System.out.println("characters copied by += (model): " + copiedByConcat);        System.out.println("characters appended by StringBuilder: " + builder.length());    }}

truecharacters copied by += (model): 499500characters appended by StringBuilder: 1000

The counter is a model of the work, not a measurement. (Java compilers can optimise one concatenation expression, but a loop that repeatedly extends a string still creates a new string on each pass.) For a string of 100,000 characters the model says 5 billion copies versus 100,000 appends. That difference is the gap between "times out" and "instant".

Also remember String.join(", ", list) for joining pieces, and String.valueOf(charArray) or new String(charArray) for turning a char[] back into a string.

A palindrome reads the same forwards and backwards: "racecar", "level". In an interview you usually have to ignore case and punctuation, so "A man, a plan, a canal: Panama" counts.

Brute force. Clean the text: build a new string with only letters and digits, lower-cased. Then reverse it and compare. This is O(n) time and O(n) extra space.

Better. Put one index at each end and move inwards. Skip characters that are not letters or digits. Compare the others. This is O(n) time and O(1) extra space, because we never build a cleaned copy. It is the first appearance of the two pointers technique, studied in detail in Two Pointers.

// File: Main.javapublic class Main {    static boolean isPalindrome(String s) {        int left = 0;        int right = s.length() - 1;        while (left < right) {            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {                left++;            }            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {                right--;            }            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {                return false;            }            left++;            right--;        }        return true;    }    public static void main(String[] args) {        String[] tests = {"racecar", "abca", "", "A man, a plan, a canal: Panama", ".,", "0P"};        for (String test : tests) {            System.out.println("[" + test + "] " + isPalindrome(test));        }    }}

[racecar] true[abca] false[] true[A man, a plan, a canal: Panama] true[.,] true[0P] false

Why does comparing the outermost pair first work? A string is a palindrome exactly when its first and last characters match and the part between them is a palindrome. So after each matching pair, we shrink the problem by two characters. The invariant is: everything outside [left, right] has already been verified to match.

Dry run on "A man, a plan" truncated to "A m,a" (so we can see the skipping):

Result: true. (The characters A, m, a do read the same backwards.) Because we only compare each character once, the time is O(n).

An empty string and a string with no letters or digits (such as ".,") are treated as palindromes. That is a decision you should state: the usual convention is yes.

Two strings are anagrams if they contain the same characters with the same counts, in any order: "listen" and "silent".

Idea 1: sort both and compare. If they are anagrams, sorting gives identical results. This takes O(n log n) time.

Idea 2: count characters. Use the frequency array from the arrays article. Add one for each character of the first string, subtract one for each character of the second. If every counter returns to zero, they are anagrams. This is O(n) time and O(1) space (26 counters).

// File: Main.javaimport java.util.Arrays;public class Main {    // Assumes both strings contain only lowercase letters a to z.    static boolean isAnagram(String a, String b) {        if (a.length() != b.length()) {            return false;        }        int[] counts = new int[26];        for (int i = 0; i < a.length(); i++) {            counts[a.charAt(i) - 'a']++;            counts[b.charAt(i) - 'a']--;        }        for (int count : counts) {            if (count != 0) {                return false;            }        }        return true;    }    static boolean isAnagramSorted(String a, String b) {        char[] x = a.toCharArray();        char[] y = b.toCharArray();        Arrays.sort(x);        Arrays.sort(y);        return Arrays.equals(x, y);    }    public static void main(String[] args) {        String[][] tests = {{"listen", "silent"}, {"rat", "car"}, {"aabb", "abab"}, {"", ""}, {"abc", "ab"}};        for (String[] pair : tests) {            System.out.println(pair[0] + " / " + pair[1] + ": " + isAnagram(pair[0], pair[1]) + " " + isAnagramSorted(pair[0], pair[1]));        }    }}

listen / silent: true truerat / car: false falseaabb / abab: true true / : true trueabc / ab: false false

The length check at the start is not only an optimisation. Without it, strings of different lengths could slip through if the counters balance in an odd way, and for the counting approach it would also cause an index error when one string is shorter.

The big assumption is "only lowercase a to z". If the input could contain upper case, digits or any other character, c - 'a' could be negative or out of range and the program would crash. Always ask what characters are possible. For arbitrary characters use a HashMap<Character, Integer>, or a larger array (for example 128 or 256 slots for ASCII or Latin-1), or sort the characters. We study the map version in Hashing.

Problem. Compress a string by replacing each run of the same character with the character followed by the length of the run, but only write the length when it is greater than 1. "aaabcc" becomes "a3bc2".

The loop uses two indexes: i marks the start of a run, and j scans to the end of the run. Then we write the character and (if needed) the count, and continue from j.

// File: Main.javapublic class Main {    static String compress(String s) {        StringBuilder out = new StringBuilder();        int i = 0;        while (i < s.length()) {            char c = s.charAt(i);            int j = i;            while (j < s.length() && s.charAt(j) == c) {                j++;            }            out.append(c);            if (j - i > 1) {                out.append(j - i);            }            i = j;        }        return out.toString();    }    public static void main(String[] args) {        String[] tests = {"aaabcc", "abc", "", "zzzzzzzzzzzz", "aabbaa"};        for (String test : tests) {            System.out.println("[" + test + "] -> [" + compress(test) + "]");        }    }}

[aaabcc] -> [a3bc2][abc] -> [abc][] -> [][zzzzzzzzzzzz] -> [z12][aabbaa] -> [a2b2a2]

Dry run for "aaabcc":

i moves to 6, which equals the length, and the loop ends. Even though there is a loop inside a loop, j never moves backwards and the next i starts from where j stopped. Every character is looked at once, so the time is O(n). The extra space is the output, which is at most about n characters.

Note that a run of 12 characters produced z12: the count is a number, written as append(int), so its digits are appended as text. This detail matters if you later try to decode the output. "a12" could mean twelve a's, and it is ambiguous when the original text contains digits. Real compression formats solve that with an escape rule. For the exercise here we assume the input has no digits.

So far we treated each char as one character. That is true for English text, and it is not true in general. Java stores text as UTF-16: each char is a 16-bit unit. Characters outside the first 65,536 (many emoji, some rare scripts) take two chars, called a surrogate pair. And what a reader sees as one letter can be several code points, such as a base letter plus a combining accent, or an Indian-language consonant plus vowel marks.

// File: Main.javapublic class Main {    public static void main(String[] args) {        String smile = "😀";                         // an emoji outside the basic range        String composed = "é";                            // e with an acute accent, as one code point        String decomposed = "é";                         // e followed by a combining accent        String hindi = "नमस्ते"; // the Hindi word namaste        System.out.println(smile.length() + " " + smile.codePointCount(0, smile.length()));        System.out.println(composed.length() + " " + decomposed.length() + " " + composed.equals(decomposed));        String normalized = java.text.Normalizer.normalize(decomposed, java.text.Normalizer.Form.NFC);        System.out.println(normalized.equals(composed));        System.out.println(hindi.length() + " " + hindi.codePointCount(0, hindi.length()));        System.out.println("TITLE".toLowerCase(java.util.Locale.ROOT));    }}

2 11 2 falsetrue6 6title

What this tells you:

• The emoji has length() 2 but is one code point. Reversing such a string with charAt would split the pair and produce garbage. StringBuilder.reverse() is aware of surrogate pairs; a hand-written loop over chars is not.
• The two spellings of "é" look identical on screen, but equals says they differ. Normalizer converts both to the same form so you can compare them.
• The Hindi word has 6 code points, but a reader would not count six letters, because vowel signs and the virama attach to the consonants around them. If a problem says "count the characters" for such text, you need to know what it means: length() code units, code points, or what readers perceive (grapheme clusters).
• toLowerCase() without a locale uses the computer's default locale, and in a Turkish locale "I" lowercases to a dotless character, not to "i". Use toLowerCase(Locale.ROOT) when you want predictable results.

For interview problems, the usual assumption is ASCII or lowercase English. It is a good habit to state that assumption aloud, and to know that a real application handling names in many languages needs more care. Most Indian-language text, for example, is outside the simple a to z model, and so are the names your users will type.

• Empty string. s.charAt(0) throws StringIndexOutOfBoundsException. Check s.isEmpty() or the length first. Also decide whether null is possible.
• Comparing with ==. Always equals.
• Discarding the result. s.trim(); alone does nothing. Write s = s.trim();.
• Building strings with += in a loop. Use StringBuilder.
• Case. Upper and lower case letters are different characters unless you normalise them. Decide whether "A" equals "a" for your problem.
• Assuming only a to z. If the input might contain anything else, c - 'a' can go negative or out of bounds.
• Off-by-one with substring. s.substring(i, j) includes i and excludes j.
• split(" ") with repeated spaces. It creates empty strings between the spaces. Use s.trim().split("\\s+") for "any amount of whitespace".
• Treating length() as the number of visible characters. It is the number of UTF-16 units.

StringBuilder sb = new StringBuilder("abc");sb.append("de").insert(0, "x").reverse().deleteCharAt(1);System.out.println(sb + " " + sb.length());

static String reverseWordsBuggy(String s) {    String[] parts = s.split(" ");    String result = "";    for (int i = parts.length - 1; i >= 0; i--) {        result += parts[i] + " ";    }    return result;}

// File: Main.javapublic class Main {    public static void main(String[] args) {        StringBuilder sb = new StringBuilder("abc");        sb.append("de").insert(0, "x").reverse().deleteCharAt(1);        System.out.println(sb + " " + sb.length());    }}

ecbax 5

// File: Main.javapublic class Main {    static int firstUniqueIndex(String s) {        int[] counts = new int[26];        for (int i = 0; i < s.length(); i++) {            counts[s.charAt(i) - 'a']++;        }        for (int i = 0; i < s.length(); i++) {            if (counts[s.charAt(i) - 'a'] == 1) {                return i;            }        }        return -1;    }    public static void main(String[] args) {        System.out.println(firstUniqueIndex("leetcode"));        System.out.println(firstUniqueIndex("loveleetcode"));        System.out.println(firstUniqueIndex("aabb"));        System.out.println(firstUniqueIndex(""));    }}

02-1-1

// File: Main.javapublic class Main {    static boolean isRotation(String a, String b) {        return a.length() == b.length() && (a + a).contains(b);    }    public static void main(String[] args) {        System.out.println(isRotation("waterbottle", "erbottlewat"));        System.out.println(isRotation("abc", "acb"));        System.out.println(isRotation("", ""));        System.out.println(isRotation("a", "ab"));        System.out.println(isRotation("abab", "baba"));    }}

truefalsetruefalsetrue

// File: Main.javapublic class Main {    static String reverseWordsBuggy(String s) {        String[] parts = s.split(" ");        String result = "";        for (int i = parts.length - 1; i >= 0; i--) {            result += parts[i] + " ";        }        return result;    }    static String reverseWords(String s) {        String trimmed = s.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();    }    public static void main(String[] args) {        String input = "  the sky   is blue ";        System.out.println("[" + reverseWordsBuggy(input) + "]");        System.out.println("[" + reverseWords(input) + "]");        System.out.println("[" + reverseWords("   ") + "]");        System.out.println("[" + reverseWords("one") + "]");    }}

[blue is   sky the   ][blue is sky the][][one]

// File: Main.javapublic class Main {    static boolean isPalindromeRange(String s, int left, int right) {        while (left < right) {            if (s.charAt(left) != s.charAt(right)) {                return false;            }            left++;            right--;        }        return true;    }    static boolean validAfterOneDeletion(String s) {        int left = 0;        int right = s.length() - 1;        while (left < right) {            if (s.charAt(left) != s.charAt(right)) {                return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);            }            left++;            right--;        }        return true;    }    public static void main(String[] args) {        String[] tests = {"aba", "abca", "abc", "deeee", "", "a", "abcdba"};        for (String test : tests) {            System.out.println("[" + test + "] " + validAfterOneDeletion(test));        }    }}

[aba] true[abca] true[abc] false[deeee] true[] true[a] true[abcdba] true

• Next: Linked Lists: Nodes, Pointers, and Pointer Reasoning introduces a structure that is not stored side by side.
• Soon: Hashing gives you map-based counting that works for any characters, and Sliding Window solves many substring problems in one pass.
• Practice habit: before you submit a string solution, test with an empty string, one character, all-same characters, and mixed case.