Question Bank
String Anagram and Palindrome
Difficulty: Medium
Five prompts on anagram detection by frequency and palindrome checks via two pointers, with one bug hunt and one canonical implementation.
String Anagram and Palindrome
Five prompts on anagram detection by frequency and palindrome checks via two pointers, with one bug hunt and one canonical implementation.
1,022 views
33
Implement isAnagram(a, b) returning true if a and b are anagrams of each other. Aim for O(n) time and O(1) extra space (assume lowercase ASCII).
Examples
Example 1:
Input: a = 'listen', b = 'silent'
Output: true
Explanation: Counts increment for a and decrement for b. Every count returns to zero, confirming the two strings have identical character multisets.Example 2:
Input: a = 'foo', b = 'bar'
Output: false
Explanation: After the increment / decrement sweep, several counts are non-zero, so the strings are not anagrams.Implement groupAnagrams(words) that returns groups of anagrams. Use a frequency-tuple key so the grouping is O(n*k) where k is the average word length.
Examples
Example 1:
Input: words = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Explanation: Each word's canonical key is its 26-length frequency tuple serialized as a string. Words sharing the same key are grouped together. O(n * k) where k is the average word length.Implement isPalindromePermutation(s) that returns true if some permutation of the lowercase-letter string s is a palindrome. Use a frequency check.
Examples
Example 1:
Input: s = 'aabbcc'
Output: true
Explanation: Every character count is even (2, 2, 2), so at most one odd count, meaning some permutation is a palindrome (e.g. 'abccba').Example 2:
Input: s = 'aabbcd'
Output: false
Explanation: 'c' and 'd' each have count 1, giving two odd counts. A palindrome allows at most one odd count, so no rearrangement works.Trace it. What does expandAroundCenter('abacaba', 3, 3) return for the function below, and what general substring is it computing?
Examples
Example 1:
Input: s = 'abacaba', left = 3, right = 3
Output: 'abacaba'
Explanation: Starting at center index 3 ('c'), the loop expands while characters match: b = b, a = a, b = b, a = a, then left = -1 exits. Returns s.substring(0, 7) = 'abacaba'. This is the odd-length palindrome expansion kernel.Spot the bug. This palindrome check is supposed to ignore non-alphanumerics and case, but it returns false for "A man, a plan, a canal: Panama".
Examples
Example 1:
Input: s = 'A man, a plan, a canal: Panama'
Output (buggy version): false
Output (fixed version): true
Explanation: The bug uses single ifs to skip non-alphanumerics; consecutive punctuation only advances once per outer iteration, and the comparison can then run on a non-alphanumeric pointer. The fix uses while loops with a shared lo < hi guard, then compares lowercased characters and advances.