algoadvance

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

Problem Statement

You are given two strings s1 and s2, both of length n. You can perform the following operations on s1 any number of times to obtain s2:

  1. Swap any two even indexed characters of s1.
  2. Swap any two odd indexed characters of s1.

Return true if you can obtain s2 from s1. Otherwise, return false.

Clarifying Questions

  1. Are the strings guaranteed to have the same length?
    • Yes, the problem states that both strings s1 and s2 are of length n.
  2. What is the range of the length n?
    • Usually, this would be detailed in the problem’s constraints, but assume it is manageable within the usual constraints for string length in such problems.
  3. Are there any constraints on the characters within s1 and s2?
    • No specific constraints, assume they can consist of any ASCII characters.

Strategy

The key insight is that you can only swap characters at even indices with other even indices and characters at odd indices with other odd indices. Therefore, for s1 to be transformable into s2, the characters at even indices in s1 should match the characters at even indices in s2, and similarly, the characters at odd indices in s1 should match the characters at odd indices in s2.

Steps:

  1. Separate the characters of s1 and s2 based on even-indexed and odd-indexed positions.
  2. Sort both groups.
  3. If the a sorted grouping of characters from s1 matches with the corresponding grouping from s2, return true; otherwise, return false.

Code

Here’s how you can implement the solution in Java:

import java.util.Arrays;

public class Solution {
    public boolean canBeEqual(String s1, String s2) {
        // If the lengths are not the same, they can never be made equal
        if (s1.length() != s2.length()) {
            return false;
        }

        // Create arrays for even and odd indexed characters
        char[] s1Even = new char[s1.length() / 2 + s1.length() % 2];
        char[] s1Odd = new char[s1.length() / 2];
        char[] s2Even = new char[s1.length() / 2 + s1.length() % 2];
        char[] s2Odd = new char[s1.length() / 2];
        
        // Populate even and odd indexed characters
        int evenIndex = 0;
        int oddIndex = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (i % 2 == 0) {
                s1Even[evenIndex] = s1.charAt(i);
                s2Even[evenIndex] = s2.charAt(i);
                evenIndex++;
            } else {
                s1Odd[oddIndex] = s1.charAt(i);
                s2Odd[oddIndex] = s2.charAt(i);
                oddIndex++;
            }
        }
        
        // Sort the arrays
        Arrays.sort(s1Even);
        Arrays.sort(s1Odd);
        Arrays.sort(s2Even);
        Arrays.sort(s2Odd);
        
        // Compare sorted arrays
        return Arrays.equals(s1Even, s2Even) && Arrays.equals(s1Odd, s2Odd);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.canBeEqual("abcd", "cdab")); // false
        System.out.println(solution.canBeEqual("abcd", "acdb")); // true
    }
}

Time Complexity

The time complexity of this solution is:

Thus, the overall complexity is O(n log n).

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