algoadvance

Leetcode 2839. Check if Strings Can be Made Equal With Operations I

Problem Statement:

Given two strings s1 and s2, check if they can be made equal by performing some number of operations. In one operation, you can swap any two adjacent characters of s1. Return true if you can make s1 equal to s2, and false otherwise.

Clarifying Questions:

1. What are the constraints on the lengths of the strings s1 and s2?
   • The lengths of s1 and s2 will be in the range [1, 1000] and they are the same length.
2. Are the strings case-sensitive?
   • Yes, the strings are case-sensitive.
3. Are there any special characters in the strings?
   • The problem does not restrict characters, so we can assume both lowercase and uppercase letters as well as any character that the language considers valid.

Strategy:

To determine if you can make s1 equal to s2 through adjacent swaps, it is equivalent to asking if s1 can be rearranged to become s2. This is a fundamental property of permutations.

Our approach will involve:

1. Check if strings s1 and s2 have the same characters with the same frequency; this would confirm that one can be rearranged to be the other.

2. If they do, return true; otherwise, return false.

Time Complexity:

• Sorting each string has a time complexity of (O(n \log n)), where (n) is the length of the strings.
• Comparing the two sorted strings has a complexity of (O(n)). Thus, the overall time complexity is (O(n \log n)).

Code:

#include <algorithm>
#include <string>

bool canBeEqualWithOperations(std::string s1, std::string s2) {
    // If lengths of s1 and s2 are different, they cannot be made equal
    if (s1.length() != s2.length()) return false;
    
    // Sort the strings
    std::sort(s1.begin(), s1.end());
    std::sort(s2.begin(), s2.end());
    
    // Compare the sorted strings
    return s1 == s2;
}

Explanation:

1. Input Check: We first check if the lengths of s1 and s2 are different. If they are, they cannot be made equal, and the function returns false.

2. Sorting: The strings s1 and s2 are sorted. Sorting rearranges the characters in a specific order (usually lexicographical).

3. Comparison: After sorting, if s1 is identical to s2, it means s1 can be rearranged to become s2, so we return true. Otherwise, return false.

This solution ensures that we can determine the equality possibility of s1 and s2 through adjacent swaps efficiently.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?