algoadvance

Leetcode 1790. Check if One String Swap Can Make Strings Equal

Problem Statement

Given two strings s1 and s2 of equal length, return true if you can swap two letters in s1 such that the result is equal to s2; otherwise, return false.

Clarifying Questions

  1. Can the strings have special characters or are they limited to only lowercase letters?
    • The problem does not specify, but typically such problems involve lowercase letters.
  2. Is it guaranteed that the lengths of s1 and s2 are equal?
    • Yes, it is mentioned in the problem statement.
  3. Do the two letters to swap have to be different?
    • No, the two letters can be the same as long as the swap results in the strings being equal.

Strategy

  1. Check if Lengths are Equal: Since the lengths are guaranteed to be equal, this check is not required.
  2. Identify Mismatched Positions: Iterate through both strings and collect the positions where the characters differ.
  3. Validate the Number of Mismatches:
    • If there are exactly two mismatched positions, check if swapping these mismatched indices in s1 makes it equal to s2.
    • If there are zero mismatched positions, it means the strings are already equal, so no swap is needed.
    • Any other number of mismatched positions will result in a false output.
  4. Edge Cases:
    • Strings with length 1 should immediately return false (if they are not identical).
    • If both strings are identical, then they technically already satisfy the conditions of the problem.

Code

public class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        
        int n = s1.length();
        List<Integer> diff = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                diff.add(i);
            }
        }
        
        // If there are no differences, the strings are already same
        if (diff.size() == 0) {
            return true;
        }
        
        // If there are exactly 2 differences, check if swapping them would make the strings equal
        if (diff.size() == 2) {
            int i = diff.get(0), j = diff.get(1);
            return s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i);
        }
        
        return false;  // For any other number of differences
    }
}

Time Complexity

The time complexity of this solution is O(n) where n is the length of the strings. This is because we only make a single pass through both strings to identify mismatched positions and perform constant-time checks.

Space Complexity

The space complexity is O(1) for the auxiliary space used (ignoring the space used by the input strings themselves). The list diff can only hold at most 2 indices, making its additional space usage constant.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI