859. Buddy Strings
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 29.1%
Problem Breakdown
The problem asks us to determine if we can swap two letters in string a such that it becomes equal to string b. The inputs are two strings a and b, both consisting of lowercase letters. The output should be a boolean value: true if the swap is possible, otherwise false.
Inputs: Two strings a and b.
Outputs: Boolean (true or false).
Implicit Constraints:
- Strings are non-empty.
- Strings contain only lowercase letters.
Intuition
A brute-force approach would involve generating all possible pairs of indices in string a, swapping them, and checking if the result matches string b. This approach is inefficient due to its high time complexity (O(n^2)) where n is the length of the strings.
The key insight is that for a swap to make a equal to b, there must be exactly two positions where the characters differ, and swapping these characters in a should result in b. Additionally, if a and b are identical, they can only be made equal by swapping duplicate characters.
Approach
- Check Lengths: If the lengths of
aandbare not equal, returnfalse. - Identify Mismatches: Traverse both strings simultaneously to find positions where characters differ.
- Count Mismatches: If there are more than two mismatches, return
false. - Check Swap Possibility:
- If there are exactly two mismatches, ensure swapping these characters in
aresults inb. - If there are no mismatches, check if
ahas duplicate characters that can be swapped.
- If there are exactly two mismatches, ensure swapping these characters in
- Return Result: Based on the above checks, return
trueorfalse.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the strings. We traverse each string once to find mismatched positions.
- Space Complexity: O(1). We use a constant amount of extra space for storing indices and counts.
Solution
def buddyStrings(a: str, b: str) -> bool:
if len(a) != len(b):
return False
# Find mismatched positions
mismatches = []
for i in range(len(a)):
if a[i] != b[i]:
mismatches.append(i)
# If there are no mismatches, check for duplicate characters
if not mismatches:
seen = set()
for char in a:
if char in seen:
return True
seen.add(char)
return False
# If there are exactly two mismatches, check if swapping them makes strings equal
if len(mismatches) == 2:
i, j = mismatches
return a[i] == b[j] and a[j] == b[i]
return False
Edge Cases Handled
- Strings of different lengths: The function immediately returns
falseif the lengths are not equal. - No mismatches (identical strings): The function checks for duplicate characters to determine if a swap is possible.
- More than two mismatches: The function returns
falseas more than one swap would be required. - Strings with only one character: Since swapping requires at least two positions, the function handles this by returning
false. - Strings with all identical characters except for two positions: The function correctly identifies these cases and checks if a swap is possible.