LeetCode 859. Buddy Strings

Description

https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/

Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

  • For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

Example 2:

Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.

Example 4:

Input: s = "aaaaaaabc", goal = "aaaaaaacb"
Output: true

Constraints:

  • 1 <= s.length, goal.length <= 2 * 104
  • s and goal consist of lowercase letters.

Explanation

There are multiple scenarios. If the string length is less than 2, return False. If all the string’s character occurs only once, return False. If the string and goal have more than 2 differences, return False.

Python Solution

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        if len(s) != len(goal):
            return False
        
        if set(s) != set(goal):
            return False
        
        if len(s) < 2:
            return False
        
        if len(s) > 1 and len(set(s)) == 1:
            return True
        
        goal_counter = {}
        for c in goal:
            goal_counter[c] = goal_counter.get(c, 0) + 1
            
        s_counter = {}
        for c in s:
            s_counter[c] = s_counter.get(c, 0) + 1
            

        all_value_only_once = True
        for key, value in s_counter.items():
            if value != 1:
                all_value_only_once = False
            if goal_counter[key] != value:
                return False
        
        if all_value_only_once and s == goal:
            return False
        
        diff_count = 0
        for c1, c2 in zip(s, goal):
            if c1 != c2:
                diff_count += 1
            
            if diff_count > 2:
                return False
         
        return True
        
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.