Skip to content

3805. Count Caesar Cipher Pairs

Description

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.

Solutions

Solution 1: String Transformation + Counting

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 \(\textit{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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countPairs(self, words: List[str]) -> int:
        cnt = defaultdict(int)
        for s in words:
            t = list(s)
            k = ord("z") - ord(t[0])
            for i in range(1, len(t)):
                t[i] = chr((ord(t[i]) - ord("a") + k) % 26 + ord("a"))
            t[0] = "z"
            cnt["".join(t)] += 1
        return sum(v * (v - 1) // 2 for v in cnt.values())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long countPairs(String[] words) {
        Map<String, Integer> cnt = new HashMap<>();
        long ans = 0;
        for (String s : words) {
            char[] t = s.toCharArray();
            int k = 'z' - t[0];
            for (int i = 1; i < t.length; i++) {
                t[i] = (char)('a' + (t[i] - 'a' + k) % 26);
            }
            t[0] = 'z';
            cnt.merge(new String(t), 1, Integer::sum);
        }
        for (int v : cnt.values()) {
            ans += 1L * v * (v - 1) / 2;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    long long countPairs(vector<string>& words) {
        unordered_map<string, int> cnt;
        long long ans = 0;
        for (auto& s : words) {
            string t = s;
            int k = 'z' - t[0];
            for (int i = 1; i < t.size(); i++) {
                t[i] = 'a' + (t[i] - 'a' + k) % 26;
            }
            t[0] = 'z';
            cnt[t]++;
        }
        for (auto& [key, v] : cnt) {
            ans += 1LL * v * (v - 1) / 2;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func countPairs(words []string) int64 {
    cnt := make(map[string]int)
    var ans int64 = 0
    for _, s := range words {
        t := []rune(s)
        k := 'z' - t[0]
        for i := 1; i < len(t); i++ {
            t[i] = 'a' + (t[i]-'a'+k)%26
        }
        t[0] = 'z'
        key := string(t)
        cnt[key]++
    }
    for _, v := range cnt {
        ans += int64(v) * int64(v-1) / 2
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countPairs(words: string[]): number {
    const cnt = new Map<string, number>();
    let ans = 0;
    for (const s of words) {
        const t = s.split('');
        const k = 'z'.charCodeAt(0) - t[0].charCodeAt(0);
        for (let i = 1; i < t.length; i++) {
            t[i] = String.fromCharCode(97 + ((t[i].charCodeAt(0) - 97 + k) % 26));
        }
        t[0] = 'z';
        const key = t.join('');
        cnt.set(key, (cnt.get(key) || 0) + 1);
    }
    for (const v of cnt.values()) {
        ans += (v * (v - 1)) / 2;
    }
    return ans;
}

Comments