Skip to content

Find Buddies in Strings

Level: L3-L4 Topics: Strings, Hashing, Modular Arithmetic, Group-By Pattern

Problem Statement

Given a list of strings, group them into "buddy" groups. Two strings are buddies if:

  1. They have the same length.
  2. The characters at corresponding positions are all the same distance apart in the alphabet.

The distance wraps around: 'a' and 'z' are distance 1 apart (going forward from 'z' wraps to 'a').

Background & Constraints

  • All strings consist of lowercase English letters ('a' to 'z').
  • The "distance" between two buddy strings is constant across all positions. For example, if the first characters differ by 3, then every pair of corresponding characters must also differ by 3.
  • Distance is directional in the sense of a shift: string s2 is a buddy of s1 if there exists some offset d such that s2[i] = (s1[i] + d) mod 26 for all i.
  • A string is always a buddy of itself (offset 0).

Examples

Example 1:

strings = ["aaa", "bbb", "zzz", "abc", "bcd", "zab"]

Buddy groups:
  Group 1: ["aaa", "bbb", "zzz"]    (all same-character strings, any offset works)
  Group 2: ["abc", "bcd", "zab"]     (each is a Caesar shift of the others)
  • "aaa" and "zzz": offset 25 (or equivalently, offset -1 mod 26). Each character: ('a' + 25) mod 26 = 'z'. Buddies.
  • "abc" and "zab": offset 25. ('a'+25)='z', ('b'+25)='a', ('c'+25)='b'. Buddies.
  • "abc" and "bbb": offset would need to be 1 for first char ('a'->'b'), but then 'b'+1='c' not 'b'. Not buddies.

Example 2:

strings = ["ab", "ba"]

"ab" → "ba" would require offset 1 for 'a'->'b' but offset -1 for 'b'->'a'.
Not buddies.

Hints & Common Pitfalls

  1. Normalize each string to a canonical form. The key insight is that buddy strings are Caesar-cipher shifts of each other. To group them, shift every string so that its first character becomes 'a', and use the result as a hash key.

  2. Canonical form: For a string s, compute: key[i] = (s[i] - s[0]) mod 26 for each position i. Two strings are buddies if and only if they produce the same key.

  3. Alternative interpretation -- consecutive differences: Instead of offset from the first character, you could compute differences between adjacent characters: diff[i] = (s[i+1] - s[i]) mod 26. This also produces a unique signature per buddy group. Both approaches are valid.

  4. Watch for negative modular arithmetic. In many languages, -1 mod 26 gives -1 instead of 25. Always add 26 before taking mod: ((s[i] - s[0]) % 26 + 26) % 26.

  5. Strings of different lengths are never buddies. You can first group by length, then by canonical form within each length group.

  6. Edge case: single-character strings. All single-character strings are buddies of each other (any offset maps one character to another). Their canonical form is always "a" (or equivalently, the empty difference sequence).

Follow-Up Questions

  1. What is the time and space complexity of the grouping algorithm? Can you do it in O(N * L) where N is the number of strings and L is the maximum string length?

  2. How would you handle uppercase letters or mixed-case strings? Should 'A' and 'a' be treated as the same character?

  3. If the alphabet is not English letters but an arbitrary set of symbols with a defined circular ordering, how does your solution generalize?

  4. Instead of grouping, suppose you are given two specific strings and must determine if they are buddies. What is the most efficient check?