Arrays

Episode 5 Valid Anagram

5 min · LeetCode 242 · Java

Title card of Episode 5: Valid Anagram

▶ This video is coming to YouTube soon.

LeetCode 242, Valid Anagram, solved on screen. We start with three examples, including the one that catches people out: the same letters aren't enough, the counts must match too. Then we sort both strings and compare them, read that code line by line, and see why it's O(n log n). Finally, one int[26] counts every letter up for s and down for t. If every count ends at zero, it's an anagram: O(n) time and O(1) space.

What you'll learn

  • What Valid Anagram asks, through three worked examples
  • Sort and compare: O(n log n) time, O(n) space
  • The key idea: anagrams have the same count of every letter
  • The int[26] counter: O(n) time, O(1) space
  • Why c - 'a' turns a letter into an array index

Chapters

  1. 0:00The problem
  2. 0:17Examples
  3. 0:54Sort and compare, visualized
  4. 1:31Sort and compare: the code
  5. 1:47Sort and compare, line by line
  6. 2:22Counting letters: the idea
  7. 2:39Counting letters, visualized
  8. 3:40Counting letters: the code
  9. 3:57Counting letters, line by line
  10. 4:42Comparing the approaches