Watch 10 video solutions for Count Caesar Cipher Pairs, a medium level problem involving Array, Hash Table, Math. This walkthrough by Sanyam IIT Guwahati has 1,331 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array words of n strings. Each string has length m and contains only lowercase English letters.
Two strings s and t are similar if we can apply the following operation any number of times (possibly zero times) so that s and t become equal.
s or t.'z' is 'a'.Count the number of pairs of indices (i, j) such that:
i < jwords[i] and words[j] are similar.Return an integer denoting the number of such pairs.
Example 1:
Input: words = ["fusion","layout"]
Output: 1
Explanation:
words[0] = "fusion" and words[1] = "layout" are similar because we can apply the operation to "fusion" 6 times. The string "fusion" changes as follows.
"fusion""gvtjpo""hwukqp""ixvlrq""jywmsr""kzxnts""layout"Example 2:
Input: words = ["ab","aa","za","aa"]
Output: 2
Explanation:
words[0] = "ab" and words[2] = "za" are similar. words[1] = "aa" and words[3] = "aa" are similar.
Constraints:
1 <= n == words.length <= 1051 <= m == words[i].length <= 1051 <= n * m <= 105words[i] consists only of lowercase English letters.Problem Overview: You are given an array of lowercase strings. Two strings form a Caesar cipher pair if one can be obtained by shifting every character of the other by the same amount in the alphabet (cyclically). The task is to count how many such pairs exist in the array.
Approach 1: Brute Force Pair Comparison (O(n² · m) time, O(1) space)
Compare every pair of strings and check whether one is a Caesar shift of the other. For two strings of length m, compute the shift using their first characters, then verify the same shift holds for every position using modular arithmetic over the alphabet. This approach performs n(n−1)/2 comparisons and scans up to m characters per comparison. It works for small inputs but quickly becomes slow when the number of strings grows.
Approach 2: String Transformation + Hash Map Counting (O(n · m) time, O(n · m) space)
Normalize each string so that all Caesar-equivalent strings produce the same canonical representation. Shift every character so the first character becomes 'a'. For example, "bcd" becomes "abc", and "xyz" also becomes "abc" after wrapping around the alphabet. This transformation takes O(m) per string. Store the normalized string in a hash map and count its frequency.
Every time you generate a normalized form, add the current frequency of that form to the answer before incrementing it. This effectively counts how many previous strings belong to the same Caesar-shift group. The hash lookup and update are O(1) on average using a hash table. Overall complexity becomes O(n · m), where n is the number of strings and m is the average string length.
This method relies on simple character arithmetic from string manipulation and modular math from math. Instead of checking pairs explicitly, it groups equivalent strings and counts combinations implicitly.
Recommended for interviews: The normalization + hash map counting approach. Interviewers expect you to recognize that Caesar-shift strings share a consistent difference pattern. Showing the brute force comparison demonstrates baseline understanding, but converting each string to a canonical form and using a hash map reduces the complexity from O(n²) to O(n) comparisons, which signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n² · m) | O(1) | Useful for understanding the Caesar shift property or when the number of strings is very small |
| String Transformation + Hash Map Counting | O(n · m) | O(n · m) | General case; groups equivalent Caesar-shift strings efficiently using hashing |