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 = 'a' and s = '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 = 'a' and s = 'b', which results in "ba" != goal.

Example 3:

Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s = 'a' and s = '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).