We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if One String Swap Can Make Strings Equal

Number: 1915

Difficulty: Easy

Paid? No

Companies: DoorDash, Meta, Amazon, Microsoft

Problem Description

Given two strings s1 and s2 of equal length, determine if it is possible to make the strings equal by performing at most one swap on exactly one of the strings. A string swap operation involves choosing two indices (which could be the same) in the string and swapping the characters at those indices.

Key Insights

  • If the strings are already equal, no swap is needed.
  • If there are exactly two positions where the strings differ, swapping the characters in one string at these positions may result in identical strings.
  • If the number of differences is any value other than 0 or 2, it's impossible to make the strings equal using a single swap.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the strings since we make a single pass to compare them. Space Complexity: O(1), only constant extra space is used to store the indices of mismatches.

Solution

The solution involves iterating over both strings simultaneously to identify the positions where they differ. If there are no differences, the strings are already equal. If there are exactly two differences, check whether swapping the characters at these positions in one string results in equality between s1 and s2. In any other case (i.e., if the number of differences is not 0 or 2), then it's impossible to achieve equality with just one swap.

Code Solutions

# Function to check if one string swap can make strings equal
def areAlmostEqual(s1: str, s2: str) -> bool:
    diff = []
    # Traverse both strings to record indices where characters differ
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            diff.append(i)
    # If the strings are already equal, return True
    if len(diff) == 0:
        return True
    # If there are exactly two differences, check if swapping makes the strings equal
    if len(diff) == 2:
        i, j = diff
        if s1[i] == s2[j] and s1[j] == s2[i]:
            return True
    # Otherwise, it's not possible with one swap
    return False

# Example usage
print(areAlmostEqual("bank", "kanb"))
← Back to All Questions