DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on

Day 22 - Determine if Two Strings Are Close

The Problem

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"
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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"
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: word1 = "cabbba", word2 = "aabbss"
Output: false
Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= word1.length, word2.length <= 105
  • word1 and word2 contain only lowercase English letters.

Tests

import pytest
from .Day22_DetermineIfTwoStringsAreClose import Solution

s = Solution()


@pytest.mark.parametrize(
    "word1,word2,expected",
    [
        ("abc", "bca", True),
        ("a", "aa", False),
        ("cabbba", "abbccc", True),
        ("cabbba", "aabbss", False),
    ],
)
def test_close_strings(word1, word2, expected):
    assert s.closeStrings(word1, word2) == expected
Enter fullscreen mode Exit fullscreen mode

Solution

def count_chars_map(word: str):
    counts = {}
    for c in word:
        if c in counts:
            counts[c] = counts[c] + 1
        else:
            counts[c] = 1
    return counts


class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        w1l = len(word1)
        w2l = len(word2)
        if w1l != w2l:
            return False
        w1_counts = count_chars_map(word1)
        w2_counts = count_chars_map(word2)

        if sorted(list(w1_counts.keys())) != sorted(list(w2_counts.keys())):
            return False

        return sorted(list(w1_counts.values())) == sorted(list(w2_counts.values()))
Enter fullscreen mode Exit fullscreen mode

Commentary

This solution was accepted but didn't perform very well. Publishing this now but plan to come back and improve it later.

Latest comments (0)