Check If String Is Transformable With Substring Sort Operations

This page explains Java solution to problem Check If String Is Transformable With Substring Sort Operations using String data structure.

Problem Statement

Given two strings s and t, you want to transform string s into string t using the following operation any number of times:

Choose a non-empty substring in s and sort it in-place so the characters are in ascending order.

For example, applying the operation on the underlined substring in 14234 results in 12344.

Return true if it is possible to transform string s into string t. Otherwise, return false.

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.ArrayList;
import java.util.List;

class CheckIfStringIsTransformableWithSubstringSortOperations {
    public boolean isTransformable(String s, String t) {
        List<Integer>[] sourceIndex = new ArrayList[10];
        for(int i = 0; i < 10; i++) sourceIndex[i] = new ArrayList<>();

        for(int i = 0; i < s.length(); i++) {
            int digit = s.charAt(i) - '0';
            sourceIndex[digit].add(i);
        }

        int[] pos = new int[10];
        for(int i = 0; i < t.length(); i++) {
            int digit = t.charAt(i) - '0';

            //Let's say digit is '1', and if target string has more 1's than source string then return false
            if(pos[digit] >= sourceIndex[digit].size()) return false;

            /**
                 All elements smaller than 'digit' should have already appeared in target string
                 Or it should be on the right side in source string

                 For e.g.
                 Source: 879
                 Target: 897

                 Now for 9 to move to left it has to be lower than 7,
                 Because only possible move is sorting elements in a window in an ascending order
            */
            for(int smallerDigit = 0; smallerDigit < digit; smallerDigit++) {
                if(pos[smallerDigit] < sourceIndex[smallerDigit].size() &&
                        sourceIndex[smallerDigit].get(pos[smallerDigit]) <
                                sourceIndex[digit].get(pos[digit])) return false;
            }
            pos[digit]++;
        }

        return true;
    }
}

Time Complexity

O(N + M) Where
N is length of input string s
M is length of input string t

Space Complexity

O(N) Where
N is length of input string s