Skip to main content
Talentd

Count Caesar Cipher Pairs - Solution & Explanation

MediumArrayHash TableMathString8 min readAsked at: Google
Practice this problem

Problem Statement

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.

  • Choose either s or t.
  • Replace every letter in the chosen string with the next letter in the alphabet cyclically. The next letter after 'z' is 'a'.

Count the number of pairs of indices (i, j) such that:

  • i < j
  • words[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 <= 105
  • 1 <= m == words[i].length <= 105
  • 1 <= n * m <= 105
  • words[i] consists only of lowercase English letters.

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n² · m)O(1)Useful for understanding the Caesar shift property or when the number of strings is very small
String Transformation + Hash Map CountingO(n · m)O(n · m)General case; groups equivalent Caesar-shift strings efficiently using hashing

Video Solution

Count Caesar Cipher Pairs | LeetCode 3805 | Weekly Contest 484 • Sanyam IIT Guwahati • 1,381 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Count Caesar Cipher Pairs easy or hard?
Count Caesar Cipher Pairs is typically classified as a Medium problem. The main challenge is recognizing that Caesar-equivalent strings share a common normalized representation, which allows the use of hash map counting instead of quadratic comparisons.
Count Caesar Cipher Pairs Python/Java solution
Most implementations normalize each string by shifting characters relative to the first character and building a new canonical string. That normalized string is used as the key in a hash map. The same logic works across Python, Java, C++, Go, and TypeScript.
How to solve Count Caesar Cipher Pairs in O(n)?
Treat each string as part of a Caesar-shift group. Normalize the string by shifting characters so its first letter becomes 'a', then use a hash map to count how many times that normalized form has appeared. Each new occurrence forms pairs with previously seen strings in the same group.
What is the best approach for Count Caesar Cipher Pairs?
The most efficient approach normalizes each string into a canonical Caesar form and counts occurrences using a hash map. By shifting characters so the first character becomes 'a', all Caesar-equivalent strings map to the same key. This reduces pair counting to a frequency problem with O(n · m) time complexity.
Is Count Caesar Cipher Pairs asked at Google/Amazon/Meta?
Problems involving string normalization, hash maps, and modular alphabet shifts appear frequently in interviews at companies like Amazon and Google. Variants of Caesar-shift grouping or shifted string grouping are common string-hashing interview questions.
What data structure is used in Count Caesar Cipher Pairs?
A hash table (hash map) is the primary data structure. It stores normalized string patterns as keys and their frequencies as values, enabling constant-time lookups while counting Caesar-equivalent pairs.
What is the time complexity of Count Caesar Cipher Pairs?
The optimal solution runs in O(n · m) time, where n is the number of strings and m is the average string length. Each string is transformed once and inserted into a hash map. The brute force comparison approach takes O(n² · m) time.

Ready to solve this problem?

Practice Count Caesar Cipher Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays