String basics

A string is an array of characters that you cannot change. So the moves from this chapter carry over: two pointers, a linear scan, a tally.

This lesson's main problem, Valid Anagram, is where most people stop at "sort both strings". Counting is faster, and it is the same tally you built in the last lesson.

Strings: three facts

• Read like an array. You read one character by its index, and the string knows its length.
• You cannot change one in place. Strings are immutable in Java, Python and TypeScript. To edit, copy the characters into an array or list, change that, then join it back.
• Letters map to numbers. Every character has a number code, and "a" is 97. Subtract the code of "a", and the letters a to z become 0 to 25.

In Java, a char is already a number, so 'c' - 'a' is 2. For many small edits, Java also has StringBuilder.

┌────────────────────────────────────────────┐
│                                            │
│   letter          a    b    c   ...    z   │
│   code           97   98   99   ...  122   │
│   code - 97       0    1    2   ...   25   │
│                                            │
└────────────────────────────────────────────┘

That last fact turns a letter into an index for an array of 26 counts.

Read the problem

Ask these before you code:

• Different lengths? They cannot be anagrams. Return false before any other work.
• Repeated letters? They count. "aab" and "abb" use the same letters, but not the same number of times.
• Upper case, spaces, emoji? Not here: only a to z. A follow-up may ask for any character.

n reaches 5 × 10⁴. O(n²) is 2.5 × 10⁹ steps, too slow. O(n log n) and O(n) both fit.

Brute force: cross out letters

For each letter of s, find a matching letter in t and cross it out. If one is missing, the answer is false.

Our example: s = "listen", t = "silent". The cells are the letters of t.

JavaPythonTypeScript

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    StringBuilder left = new StringBuilder(t); // letters of t not matched yet
    for (char ch : s.toCharArray()) {
        int i = left.indexOf(String.valueOf(ch)); // a hidden loop over t
        if (i == -1) return false;
        left.setCharAt(i, '.'); // cross it out
    }
    return true;
}

The loop runs n times, and each search scans up to n cells. (In Python, in and index each scan, so twice the work, but the same growth.) So O(n²): about 2.5 × 10⁹ steps at the limit.

Better: sort both

Sorting puts equal letters side by side, so two anagrams sort to the same string. "listen" and "silent" both become "eilnst".

JavaPythonTypeScript

char[] a = s.toCharArray();
char[] b = t.toCharArray();
Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);

• Java sorts a char[] by character code. Python's sorted(s) returns a sorted list of the characters.
• In TypeScript, the default sort() compares text, which is right for letters. (The trap with numbers is in The TypeScript toolbox for DSA.)

Cost: O(n log n) time and O(n) space for the arrays. It fits, but it puts every letter in order when the question never asked about order.

The key insight: count, do not order

Two strings are anagrams when every letter appears the same number of times in both. That is the tally from the last lesson.

Use one array of 26 counts:

• Each letter of s adds 1.
• Each letter of t takes 1 away.
• If the strings are anagrams, every count ends at 0.

Optimal: one array of 26 counts

1. If the lengths differ, return false.
2. Make 26 counts, all 0.
3. Walk both strings together: add 1 for s[i], take 1 for t[i].
4. Return true when every count is 0.

The cells are the letters of s. The side store shows only the counts that are not 0.

JavaPythonTypeScript

boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++; // a letter of s adds one
        count[t.charAt(i) - 'a']--; // a letter of t takes one away
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

• Time: one walk of n steps, then 26 checks. O(n).
• Space: 26 counts, whatever the length. That is O(1).
• Any character (the follow-up): use a hash map instead of 26 slots (HashMap<Character, Integer>, dict, Map<string, number>). Same idea, O(k) space for k different characters.
• In Python, Counter(s) == Counter(t) does the whole check in one line, with a hash map inside.

Side by side

Other string moves

The rest of this lesson's list uses moves you already know, plus two new tricks.

Two pointers from both ends

Reverse a String II gives the string as an array of characters. Reverse it in place exactly as you reversed an array in First array problems.

Palindrome Check uses the same two pointers, but compares instead of swapping:

┌──────────────────────────────────────────────┐
│                                              │
│   h   a   n   n   a   h                      │
│   l                   r     h = h, step in   │
│       l           r         a = a, step in   │
│           l   r             n = n, step in   │
│           r   l             crossed: true    │
│                                              │
└──────────────────────────────────────────────┘

JavaPythonTypeScript

boolean isPalindrome(String s) {
    int l = 0;
    int r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

Scan from the right

Largest Odd Number in a String: a number is odd when its last digit is odd, and a longer number (with no leading zeros) is larger. So find the rightmost odd digit and keep everything up to it.

• "35427" stays "35427".
• "4206" has no odd digit, so the answer is "".

Compare column by column

Longest Common Prefix: read the first string one position at a time. At each position, check that every string has the same character there. Stop at the first mismatch. ["flower", "flow", "flight"] gives "fl".

Two maps

Isomorphic Strings: each character of s must turn into exactly one character of t, and no two characters may turn into the same one. Keep a map from s to t and a map from t to s.

• "egg" and "add" pass.
• "badc" and "baba" fail. Only the second map catches it: b and d would both turn into b.

Double the string

Rotate String: every rotation of s sits inside s + s.

┌────────────────────────────────────────────┐
│                                            │
│      s         a b c d e                   │
│      s + s     a b c d e a b c d e         │
│                    └───────┘               │
│      goal          c d e a b    found      │
│                                            │
└────────────────────────────────────────────┘

JavaPythonTypeScript

boolean isRotation(String s, String goal) {
    return s.length() == goal.length() && (s + s).contains(goal);
}

The length check matters: "a" is inside "aa" + "aa", but "a" is not a rotation of "aa".

Count, then sort

Sort Characters by Frequency: count each character with a hash map, sort the entries by count from high to low, then repeat each character by its count. "tree" becomes "eetr". Sorting k distinct characters costs O(k log k), small next to the O(n) count.

How to spot this pattern

Before any of these, read the character set in the limits. "Lowercase English letters" means 26 counts. "Any character" means a hash map.

Read more

• String on MDN, including why strings cannot be changed in place
• String.prototype.charCodeAt() on MDN, the letter-to-number step
• Valid Anagram on takeUforward, to solve it yourself
• Rotate String on takeUforward, to try the s + s trick

Next: a new chapter, starting with "What is recursion?": a function that calls itself, and the call stack that keeps track.