Determine if Two Strings Are Close

LeetCode 1777 | Difficulty: Medium

Medium

Problem Description

Two strings are considered close if you can attain one from the other using the following operations:

- Operation 1: Swap any two **existing** characters.



    - For example, `abcde -> aecdb`





- Operation 2: Transform **every** occurrence of one **existing** character into another **existing** character, and do the same with the other character.


    - For example, `aacabb -> bbcbaa` (all `a`'s turn into `b`'s, and all `b`'s turn into `a`'s)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Example 2:

Input: word1 = "a", word2 = "aa"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: You can attain word2 from word1 in 3 operations.
Apply Operation 1: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"

Constraints:

- `1 <= word1.length, word2.length <= 10^5`

- `word1` and `word2` contain only lowercase English letters.

Topics: Hash Table, String, Sorting, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 176 ms)

Metric	Value
Runtime	176 ms
Memory	45.1 MB
Date	2022-01-03

Solution

public class Solution {
    public bool CloseStrings(string word1, string word2) {
        if(word1.Length != word2.Length) return false;
    
    Dictionary<char, int> freq1 = new Dictionary<char, int>();
    Dictionary<char, int> freq2 = new Dictionary<char, int>();
    for (int i = 0; i < word1.Length; i++)
    {
        if(freq1.ContainsKey(word1[i]))
        {
            freq1[word1[i]]++;
        }
        else freq1.Add(word1[i],1);

        if (freq2.ContainsKey(word2[i]))
        {
            freq2[word2[i]]++;
        }
        else freq2.Add(word2[i], 1);
    }
    if(freq1.Count != freq1.Count) return false;

    if(freq1.Keys.OrderBy(x=>x).ToList().SequenceEqual(freq2.Keys.OrderBy(y=>y).ToList())
    && freq1.Values.OrderBy(x=>x).ToList().SequenceEqual(freq2.Values.OrderBy(y=>y).ToList()))
    {
        return true;
    }
    
    return false;
    }
}

📜 1 more C# submission(s)

Submission (2022-01-03) — 234 ms, 41.7 MB

public class Solution {
    public bool CloseStrings(string word1, string word2) {
        if(word1.Length != word2.Length) return false;
    
    Dictionary<char, int> freq1 = new Dictionary<char, int>();
    Dictionary<char, int> freq2 = new Dictionary<char, int>();
    for (int i = 0; i < word1.Length; i++)
    {
        if(freq1.ContainsKey(word1[i]))
        {
            freq1[word1[i]]++;
        }
        else freq1.Add(word1[i],1);

        if (freq2.ContainsKey(word2[i]))
        {
            freq2[word2[i]]++;
        }
        else freq2.Add(word2[i], 1);
    }
    if(freq1.Count != freq2.Count) return false;

    if(freq1.Keys.OrderBy(x=>x).ToList().SequenceEqual(freq2.Keys.OrderBy(y=>y).ToList())
    && freq1.Values.OrderBy(x=>x).ToList().SequenceEqual(freq2.Values.OrderBy(y=>y).ToList()))
    {
        return true;
    }
    
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Operation 1 allows you to freely reorder the string.

Hint 2: Operation 2 allows you to freely reassign the letters' frequencies.