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.
We can transform each string into a unified form. Specifically, we convert the first character of the string to 'z', and then transform the other characters in the string with the same offset. This way, all similar strings will be transformed into the same form. We use a hash table cnt to record the number of occurrences of each transformed string.
Finally, we iterate through the hash table, calculate the combination number \frac{v(v-1)}{2} for each string's occurrence count v, and add it to the answer.
The time complexity is O(n times m) and the space complexity is O(n times m), where n is the length of the string array and m is the length of the strings.
Python
Java
C++
Go
TypeScript
| 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 |
Count Caesar Cipher Pairs | LeetCode 3805 | Weekly Contest 484 • Sanyam IIT Guwahati • 1,331 views views
Watch 9 more video solutions →Practice Count Caesar Cipher Pairs with our built-in code editor and test cases.
Practice on FleetCode