Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 42s17 days 22 hours 18 minutes 42 seconds.

Algorithms - Strings · 4:07

Frequency Arrays, Anagrams and Palindromes

Counting characters with a frequency array cnt[26]: two words are anagrams exactly when their count arrays are equal, a sliding window finds every anagram of a pattern in O(n + m) by updating two counters per step, and letters can be rearranged into a palindrome when at most one count is odd. Then palindromes from the outside in (two pointers, and a near miss that must try both deletions) and from the inside out (expanding around odd and even centres on abababc and cbaabd, after cp-algorithms.com), and the quadratic cost of expanding every centre of aaa...a, measured, which Manacher's algorithm later removes.

You will learn

Build a frequency array in one pass and use it to test anagrams and palindrome rearrangements
Find all anagrams of a pattern in a text in O(n + m) with a sliding count window
Check palindromes with two pointers, including the at-most-k-deletions variant that must try both sides
Enumerate palindromic substrings by expanding around both odd and even centres, and explain why it is O(n^2) in the worst case

Chapters

PreviousC++ Strings NextTries