LeetCode 1585: Check If String Is Transformable With Substring Sort Operations Solution

LeetCode 1585 Solution Explanation

Explanation

To solve this problem, we can iterate over both strings from left to right and keep track of the indices where each digit occurs in both strings. We need to ensure that the relative order of digits in s is the same as in t.

We can achieve this by ensuring that for each digit d, the number of occurrences of d in s before the current index should be less than or equal to the number of occurrences of d in t before the current index.

We can use a data structure like an array or a hashmap to keep track of the indices of each digit in both strings. Then, we iterate over the strings and check if the constraint mentioned above is satisfied.

If at any point, the constraint is violated, then it is not possible to transform s into t, and we return false. Otherwise, we return true at the end.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the strings s and t.

Space Complexity

The space complexity is O(1) because we are using a fixed-size array or hashmap to store the occurrences of digits.

LeetCode 1585 Solutions in Java, C++, Python

public boolean isTransformable(String s, String t) {
    int n = s.length();
    
    int[] sIndices = new int[10];
    int[] tIndices = new int[10];
    
    for (int i = 0; i < n; i++) {
        int d = s.charAt(i) - '0';
        
        if (sIndices[d] >= tIndices[d]) {
            sIndices[d]++;
        } else {
            for (int j = d - 1; j >= 0; j--) {
                if (sIndices[j] < tIndices[j]) {
                    return false;
                }
            }
            
            tIndices[d]++;
        }
    }
    
    return true;
}

Interactive Code Editor for LeetCode 1585

Improve Your LeetCode 1585 Solution

Use the editor below to refine the provided solution for LeetCode 1585. Select a programming language and try the following:

Add import statements if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...

Sign in with Google

LeetCode 1585: Check If String Is Transformable With Substring Sort Operations