Check if Strings Can be Made Equal With Operations II

Problem Description

You are given two strings s1 and s2, both of length n, consisting of lowercase English letters. You can apply the following operation on any of the two strings any number of times: Choose any two indices i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string. Return true if you can make the strings s1 and s2 equal, and false otherwise.

Key Insights

• The allowable swaps can only occur between characters at even indices or odd indices.
• To determine if the two strings can be made equal, we need to check the characters at even indices and odd indices separately.
• If the sorted characters at even indices of both strings are the same, and the sorted characters at odd indices of both strings are the same, then the strings can be made equal.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting of characters at even and odd indices. Space Complexity: O(n) - for storing characters at even and odd indices.

Solution

To check if the two strings can be made equal, we will:

1. Separate the characters of both strings into even-indexed and odd-indexed groups.
2. Sort these groups for both strings.
3. Compare the sorted lists; if they match for both even and odd groups, then the strings can be made equal.

We'll use arrays to store the characters at even and odd indices.

Code Solutions