9.04Beginner / Intermediate7 topics18 min7 interactive animations

Character patterns

Character-level patterns: frequency counts, case conversion, alphanumeric filtering, anagrams, palindromes, isomorphic strings and uniqueness checks. Most use a counting array or two pointers and run in O(n).

Learning goals

Count characters with an int[26] or int[128]
Convert case and filter characters with ASCII arithmetic
Check anagrams, palindromes and isomorphism in linear time
Test uniqueness with a bitmask

Prerequisites

Core operationsArrays

9.04.1

Frequency counts

A frequency count records how often each character occurs. For lowercase letters use int[26] indexed by c - 'a'; for ASCII use int[128]; for arbitrary characters use a HashMap<Character, Integer>. One pass, O(n) time and O(alphabet) space.

Count the letters of a string and read the most frequent character.

Java

1int[] freq = new int[26];
2for (char c : s.toCharArray()) freq[c - 'a']++;
3int best = 0;
4for (int i = 1; i < 26; i++) if (freq[i] > freq[best]) best = i;
5char mostFrequent = (char) ('a' + best);

Character counts and uniqueness with a bitmask

Interactive · edit the input

char[] s · length 11

012345678910

ReadingCounted / newRepeated characterRepeated

freq[c]

empty

Setup

One counter per possible character: increment the counter of each character read.

Step 1 / 13

Java

1int[] freq = new int[128];                       // one counter per ASCII character
2for (char c : s.toCharArray()) freq[c]++;
3// uniqueness of lowercase letters with one int as a set of 26 bits
4int seen = 0;
5for (char c : s.toCharArray()) {
6    int bit = 1 << (c - 'a');
7    if ((seen & bit) != 0) return false;        // bit already set: repeated
8    seen |= bit;
9}
10return true;

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L1		One counter per possible character: increment the counter of each character read.
2	L2	i=0 c='m' count=1	freq['m'] becomes 1.
3	L2	i=1 c='i' count=1	freq['i'] becomes 1.
4	L2	i=2 c='s' count=1	freq['s'] becomes 1.
5	L2	i=3 c='s' count=2	freq['s'] becomes 2.
6	L2	i=4 c='i' count=2	freq['i'] becomes 2.
7	L2	i=5 c='s' count=3	freq['s'] becomes 3.
8	L2	i=6 c='s' count=4	freq['s'] becomes 4.
9	L2	i=7 c='i' count=3	freq['i'] becomes 3.
10	L2	i=8 c='p' count=1	freq['p'] becomes 1.
11	L2	i=9 c='p' count=2	freq['p'] becomes 2.
12	L2	i=10 c='i' count=4	freq['i'] becomes 4.
13	L2	distinct=4 return=i:4	4 distinct characters; 'i' is the most frequent (4). One pass, O(n) time, O(alphabet) space.

9.04.2

Case conversion

Character.toLowerCase(c), Character.toUpperCase(c) and s.toLowerCase() convert case; for ASCII letters you can also add or subtract 32, or flip bit 5 with c ^ 32 (only valid for letters). Prefer the library methods for non-ASCII text, because case rules are locale-dependent.

Switch the animation to Toggle case to see the XOR 32 trick.

Java

1char lower = (char) (c | 32);              // 'A' (65) -> 'a' (97), only valid for letters
2char flipped = (char) (c ^ 32);            // toggles the case of a letter
3String s1 = "Hello".toLowerCase();         // "hello"
4boolean up = Character.isUpperCase('Q');   // true

A char is a number: codes, c - 'a' and case flipping

Interactive · edit the input

char[] s · length 5

␠

01234

Being comparedAlready checked

Setup

Every char is a number. In ASCII 'a' = 97, 'A' = 65, '0' = 48. Subtracting a base character gives an index.

Step 1 / 7

Java

1for (int i = 0; i < s.length(); i++) {
2    char c = s.charAt(i);
3    int code = c;                        // widening: the character's numeric code
4    int index = c - 'a';                 // 0..25 for lowercase letters
5    int digit = c - '0';                 // 0..9 for digits
6}
7// toggle ASCII case: flip bit 5 (value 32); letters only
8char flipped = (char) (c ^ 32);          // 'a' (97) <-> 'A' (65)

Live state

length

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L1	length=5	Every char is a number. In ASCII 'a' = 97, 'A' = 65, '0' = 48. Subtracting a base character gives an index.
2	L4	i=0 c='a' code=97 c - 'a'=0 c - '0'=-	'a' is 97; 97 - 97 = 0 is its position in the alphabet.
3	L3	i=1 c='Z' code=90 c - 'a'=- c - '0'=-	'Z' is 90, an uppercase letter (65-90).
4	L5	i=2 c='5' code=53 c - 'a'=- c - '0'=5	'5' is 53; 53 - 48 = 5 is the digit's value.
5	L3	i=3 c=' ' code=32 c - 'a'=- c - '0'=-	' ' is 32, not a letter or digit.
6	L4	i=4 c='b' code=98 c - 'a'=1 c - '0'=-	'b' is 98; 98 - 97 = 1 is its position in the alphabet.
7	L6	return=[97, 90, 53, 32, 98]	Characters are compared, sorted and used as array indexes through these numeric codes.

9.04.3

Alphanumeric filtering

Filtering keeps only letters and digits, dropping spaces and punctuation, often before a palindrome or anagram check. Test with Character.isLetterOrDigit(c) or the ASCII ranges, and append the kept characters to a StringBuilder. One pass, O(n).

The Both option applies the same steps as the lenient palindrome check.

Java

1StringBuilder out = new StringBuilder();
2for (char c : s.toCharArray()) {
3    if (Character.isLetterOrDigit(c)) out.append(Character.toLowerCase(c));
4}
5String cleaned = out.toString();   // "A man, a plan!" -> "amanaplan"

Lowercasing and filtering alphanumeric characters

Interactive · edit the input

char[] s · length 14

␠

012345678910111213

ReadingKeptDropped

out

empty

Setup

Drop everything that is not a letter or digit. Map A-Z to a-z by adding 32.

Step 1 / 16

Java

1StringBuilder out = new StringBuilder();
2for (char c : s.toCharArray()) {
3    boolean alnum = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
4    if (filter && !alnum) continue;                      // drop punctuation and spaces
5    if (lower && c >= 'A' && c <= 'Z') c = (char) (c + 32);   // ASCII lowercase
6    out.append(c);
7}

Live state

filter

true

lower

true

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L1	filter=true lower=true	Drop everything that is not a letter or digit. Map A-Z to a-z by adding 32.
2	L5	i=0 c='A' alnum=true	'A' becomes 'a' (+32) and is appended.
3	L4	i=1 c=' ' alnum=false	' ' is not a letter or digit: dropped.
4	L6	i=2 c='m' alnum=true	'm' is appended unchanged.
5	L6	i=3 c='a' alnum=true	'a' is appended unchanged.
6	L6	i=4 c='n' alnum=true	'n' is appended unchanged.
7	L4	i=5 c=',' alnum=false	',' is not a letter or digit: dropped.
8	L4	i=6 c=' ' alnum=false	' ' is not a letter or digit: dropped.
9	L6	i=7 c='a' alnum=true	'a' is appended unchanged.
10	L4	i=8 c=' ' alnum=false	' ' is not a letter or digit: dropped.
11	L6	i=9 c='p' alnum=true	'p' is appended unchanged.
12	L6	i=10 c='l' alnum=true	'l' is appended unchanged.
13	L6	i=11 c='a' alnum=true	'a' is appended unchanged.
14	L6	i=12 c='n' alnum=true	'n' is appended unchanged.
15	L4	i=13 c='!' alnum=false	'!' is not a letter or digit: dropped.
16	L7	return="amanaplan"	Result "amanaplan". One pass, O(n). Prefer these ASCII checks over locale-sensitive methods when the data is ASCII.

9.04.4

Anagrams

Two strings are anagrams when they contain the same letters with the same counts. Sorting both and comparing costs O(n log n); a counting array does it in O(n): add the letters of s, subtract those of t, and fail as soon as a count goes negative. Different lengths are never anagrams.

Try the not-anagram and different-length presets.

Java

1static boolean isAnagram(String s, String t) {
2    if (s.length() != t.length()) return false;
3    int[] count = new int[26];
4    for (char c : s.toCharArray()) count[c - 'a']++;
5    for (char c : t.toCharArray()) if (--count[c - 'a'] < 0) return false;
6    return true;
7}

Anagram check with a counting array

Interactive · edit the input

char[] s · length 6

012345

ReadingCountedNo matching letter left

t = "silent"

Check

Equal lengths: an anagram is still possible.

Step 1 / 14

Java

1static boolean isAnagram(String s, String t) {
2    if (s.length() != t.length()) return false;
3    int[] count = new int[26];
4    for (char c : s.toCharArray()) count[c - 'a']++;          // add s
5    for (char c : t.toCharArray()) {
6        if (--count[c - 'a'] < 0) return false;               // t uses a letter s does not have
7    }
8    return true;                                              // equal length and never negative: all zero
9}

Live state

s.length()

t.length()

s.length() == t.length()true

Execution trace (dry run table)Show 14 steps

Step	Line	State	What happens
1	L2	s.length()=6 t.length()=6	Equal lengths: an anagram is still possible.
2	L4	i=0 c='l'	count['l'] = 1.
3	L4	i=1 c='i'	count['i'] = 1.
4	L4	i=2 c='s'	count['s'] = 1.
5	L4	i=3 c='t'	count['t'] = 1.
6	L4	i=4 c='e'	count['e'] = 1.
7	L4	i=5 c='n'	count['n'] = 1.
8	L6	j=0 c='s' count['s']=0	Cancel one 's': count is now 0.
9	L6	j=1 c='i' count['i']=0	Cancel one 'i': count is now 0.
10	L6	j=2 c='l' count['l']=0	Cancel one 'l': count is now 0.
11	L6	j=3 c='e' count['e']=0	Cancel one 'e': count is now 0.
12	L6	j=4 c='n' count['n']=0	Cancel one 'n': count is now 0.
13	L6	j=5 c='t' count['t']=0	Cancel one 't': count is now 0.
14	L8	return=true	Every letter of t cancelled one letter of s and the lengths match, so all counts are zero: anagrams. O(n) time, O(26) space.

9.04.5

Palindrome checks

A palindrome reads the same forwards and backwards. Use two pointers that move inward and compare characters: O(n) time, O(1) space. The lenient version skips non-alphanumeric characters and ignores case, as in “A man, a plan, a canal: Panama”.

Run both modes on the same text and compare.

Java

1static boolean isPalindrome(String s) {
2    int lo = 0, hi = s.length() - 1;
3    while (lo < hi) {
4        while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
5        while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
6        if (Character.toLowerCase(s.charAt(lo++)) != Character.toLowerCase(s.charAt(hi--))) return false;
7    }
8    return true;
9}

Palindrome check with two pointers

Interactive · edit the input

char[] s · length 30

␠

01234567891011121314151617181920212223242526272829

ComparingMatched pairMismatchSkipped

Setup

Compare from both ends inward, skipping anything that is not a letter or digit and ignoring case.

Step 1 / 21

Java

1static boolean isPalindrome(String s, boolean lenient) {
2    int lo = 0, hi = s.length() - 1;
3    while (lo < hi) {
4        if (lenient && !isAlnum(s.charAt(lo))) { lo++; continue; }
5        if (lenient && !isAlnum(s.charAt(hi))) { hi--; continue; }
6        char a = s.charAt(lo), b = s.charAt(hi);
7        if (lenient) { a = Character.toLowerCase(a); b = Character.toLowerCase(b); }
8        if (a != b) return false;
9        lo++; hi--;
10    }
11    return true;
12}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L2	lo=0 hi=29	Compare from both ends inward, skipping anything that is not a letter or digit and ignoring case.
2	L8	lo=0 hi=29 a='a' b='a'	'a' = 'a': this pair matches.
3	L4	lo=1 hi=28 s[lo]=' '	' ' is not a letter or digit: skip it on the left.
4	L8	lo=2 hi=28 a='m' b='m'	'm' = 'm': this pair matches.
5	L8	lo=3 hi=27 a='a' b='a'	'a' = 'a': this pair matches.
6	L8	lo=4 hi=26 a='n' b='n'	'n' = 'n': this pair matches.
7	L4	lo=5 hi=25 s[lo]=','	',' is not a letter or digit: skip it on the left.
8	L4	lo=6 hi=25 s[lo]=' '	' ' is not a letter or digit: skip it on the left.
9	L8	lo=7 hi=25 a='a' b='a'	'a' = 'a': this pair matches.
10	L4	lo=8 hi=24 s[lo]=' '	' ' is not a letter or digit: skip it on the left.
11	L8	lo=9 hi=24 a='p' b='p'	'p' = 'p': this pair matches.
12	L5	lo=10 hi=23 s[hi]=' '	' ' is not a letter or digit: skip it on the right.
13	L5	lo=10 hi=22 s[hi]=':'	':' is not a letter or digit: skip it on the right.
14	L8	lo=10 hi=21 a='l' b='l'	'l' = 'l': this pair matches.
15	L8	lo=11 hi=20 a='a' b='a'	'a' = 'a': this pair matches.
16	L8	lo=12 hi=19 a='n' b='n'	'n' = 'n': this pair matches.
17	L4	lo=13 hi=18 s[lo]=','	',' is not a letter or digit: skip it on the left.
18	L4	lo=14 hi=18 s[lo]=' '	' ' is not a letter or digit: skip it on the left.
19	L8	lo=15 hi=18 a='a' b='a'	'a' = 'a': this pair matches.
20	L4	lo=16 hi=17 s[lo]=' '	' ' is not a letter or digit: skip it on the left.
21	L11	return=true	The pointers met without a mismatch: it is a palindrome. O(n) time, O(1) space.

9.04.6

Isomorphism

Two strings are isomorphic when the characters of one can be replaced consistently to get the other: each letter must map to exactly one letter and no two letters may map to the same one. Keep two maps (s to t and t to s) and check both on every position. O(n) time.

Use the conflict presets to see each direction fail.

Java

1static boolean isomorphic(String s, String t) {
2    if (s.length() != t.length()) return false;
3    Map<Character, Character> st = new HashMap<>(), ts = new HashMap<>();
4    for (int i = 0; i < s.length(); i++) {
5        char a = s.charAt(i), b = t.charAt(i);
6        if (st.containsKey(a) && st.get(a) != b) return false;
7        if (ts.containsKey(b) && ts.get(b) != a) return false;
8        st.put(a, b); ts.put(b, a);
9    }
10    return true;
11}

Isomorphic strings: two mappings must agree

Interactive · edit the input

char[] s · length 3

012

ReadingMapped consistentlyConflict

t (second string)

st: s → t

empty

ts: t → s

empty

Setup

Each letter of s must always map to the same letter of t, and no two different letters may map to the same one, so check both directions.

Step 1 / 11

Java

1static boolean isomorphic(String s, String t) {
2    if (s.length() != t.length()) return false;
3    Map<Character, Character> st = new HashMap<>(), ts = new HashMap<>();
4    for (int i = 0; i < s.length(); i++) {
5        char a = s.charAt(i), b = t.charAt(i);
6        if (st.containsKey(a) && st.get(a) != b) return false;   // a already maps elsewhere
7        if (ts.containsKey(b) && ts.get(b) != a) return false;   // b is already used by another letter
8        st.put(a, b); ts.put(b, a);
9    }
10    return true;
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L3		Each letter of s must always map to the same letter of t, and no two different letters may map to the same one, so check both directions.
2	L6	i=0 a='e' b='a'	'e' has no mapping yet.
3	L7	i=0 a='e' b='a'	'a' has no preimage yet.
4	L8	i=0	Record 'e' → 'a' in both maps.
5	L6	i=1 a='g' b='d'	'g' has no mapping yet.
6	L7	i=1 a='g' b='d'	'd' has no preimage yet.
7	L8	i=1	Record 'g' → 'd' in both maps.
8	L6	i=2 a='g' b='d'	'g' → 'd' agrees with the existing mapping.
9	L7	i=2 a='g' b='d'	'd' ← 'g' agrees.
10	L8	i=2	Record 'g' → 'd' in both maps.
11	L10	return=true	Both mappings stayed consistent: the strings are isomorphic. O(n) time.

9.04.7

Uniqueness

To test whether all characters are unique, use a set, a counting array, or for lowercase letters a bitmask held in one int: test the bit for the character, return false if it is set, otherwise set it. O(n) time and O(1) space, and since only 26 letters exist, any longer string must repeat.

Switch to the bitmask method and try “leetcode”.

Java

1static boolean allUnique(String s) {          // lowercase letters only
2    if (s.length() > 26) return false;
3    int seen = 0;
4    for (char c : s.toCharArray()) {
5        int bit = 1 << (c - 'a');
6        if ((seen & bit) != 0) return false;
7        seen |= bit;
8    }
9    return true;
10}

Character counts and uniqueness with a bitmask

Interactive · edit the input

char[] s · length 11

012345678910

ReadingCounted / newRepeated characterRepeated

freq[c]

empty

Setup

One counter per possible character: increment the counter of each character read.

Step 1 / 13

Java

1int[] freq = new int[128];                       // one counter per ASCII character
2for (char c : s.toCharArray()) freq[c]++;
3// uniqueness of lowercase letters with one int as a set of 26 bits
4int seen = 0;
5for (char c : s.toCharArray()) {
6    int bit = 1 << (c - 'a');
7    if ((seen & bit) != 0) return false;        // bit already set: repeated
8    seen |= bit;
9}
10return true;

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L1		One counter per possible character: increment the counter of each character read.
2	L2	i=0 c='m' count=1	freq['m'] becomes 1.
3	L2	i=1 c='i' count=1	freq['i'] becomes 1.
4	L2	i=2 c='s' count=1	freq['s'] becomes 1.
5	L2	i=3 c='s' count=2	freq['s'] becomes 2.
6	L2	i=4 c='i' count=2	freq['i'] becomes 2.
7	L2	i=5 c='s' count=3	freq['s'] becomes 3.
8	L2	i=6 c='s' count=4	freq['s'] becomes 4.
9	L2	i=7 c='i' count=3	freq['i'] becomes 3.
10	L2	i=8 c='p' count=1	freq['p'] becomes 1.
11	L2	i=9 c='p' count=2	freq['p'] becomes 2.
12	L2	i=10 c='i' count=4	freq['i'] becomes 4.
13	L2	distinct=4 return=i:4	4 distinct characters; 'i' is the most frequent (4). One pass, O(n) time, O(alphabet) space.

Practice ladder

Now try it yourself

Easy

Count the vowels of a string
Is "racecar" a palindrome? Is "Racecar"?

Medium

Group the words [eat, tea, tan, ate, nat, bat] into anagram classes
Check “egg” and “add” for isomorphism, then “foo” and “bar”

Advanced

Find the longest palindromic substring in O(n²) by expanding around centres

Key takeaways

int[26] or int[128] counters make character problems O(n).
Anagrams compare counts, palindromes use two pointers, isomorphism needs two maps.
A bitmask tests uniqueness of 26 letters in O(1) space.