Problem Statement
Two strings are called buddy strings if the distance between every pair of consecutive characters is the same (cyclic, wrapping around from 'z' to 'a').
The cyclic distance between two characters is defined as (char2 - char1 + 26) % 26.
Given a list of strings (all same length), group all buddy strings together.
Constraints
1 <= strs.length <= 10^41 <= strs[i].length <= 100- All strings have the same length
- Strings consist of lowercase English letters only
Examples
Buddy strings:
"aaa"and"zzz"— distance between each consecutive pair:(z-a+26)%26 = 25for both. Same pattern."abc"and"xyz"— distances:(b-a)=1, (c-b)=1and(y-x)=1, (z-y)=1. Same pattern.
Not buddy strings:
"aaa"and"zzy"—"aaa"has distances[0,0],"zzy"has distances[0,25]. Different.
Example
Input:
strs = ["abc", "xyz", "aaa", "zzz", "bcd", "ace", "zzy"]
Output:
[["abc", "xyz", "bcd"], ["aaa", "zzz"], ["ace"], ["zzy"]]
Explanation:
"abc","xyz","bcd"all have consecutive distances[1, 1]"aaa","zzz"both have consecutive distances[0, 0]"ace"has distances[2, 2]— no other string matches"zzy"has distances[0, 25]— no other string matches
What the Interviewer Expects
- Identify the key insight — two strings are buddies if their sequence of consecutive character distances (mod 26) is identical.
- Hash by distance pattern — compute the distance array for each string and use it as a grouping key in a HashMap.
- Handle the modular arithmetic — ensure wrapping works correctly with
(char[i+1] - char[i] + 26) % 26. - Time complexity — O(n * m) where n = number of strings, m = string length.
Follow-ups
- What if the definition changes to absolute distance (not cyclic)? Does your approach still work?
- What if strings can have different lengths? How would you handle grouping?
- Can you solve this without explicitly storing the distance array — using a canonical form instead?
- How would you handle this for very large inputs (10M+ strings) that don't fit in memory?