Leetcode 833. Find And Replace in String

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

1. 0 <= indexes.length = sources.length = targets.length <= 100
2. 0 < indexes[i] < S.length <= 1000
3. All characters in given inputs are lowercase letters.

Code (Java):

class Solution {
    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        // create tuple and sort
        //
        Tuple[] tuples = new Tuple[indexes.length]; 
        for (int i = 0; i < indexes.length; i++) {
            Tuple tuple = new Tuple(indexes[i], sources[i], targets[i]);
            tuples[i] = tuple;
        }

        Arrays.sort(tuples, new MyTupleComparator());
        
        int prev = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indexes.length; i++) {
            int index = tuples[i].index;
            String source = tuples[i].source;
            String target = tuples[i].target;

            if (S.substring(index, index + source.length()).equals(source)) {
                // prev seg 
                //
                sb.append(S.substring(prev, index));

                // curr seg 
                //
                sb.append(target);
                prev = index + source.length();
            }
        }

        sb.append(S.substring(prev));

        return sb.toString();
    }
}

class Tuple {
    int index;
    String source;
    String target;

    public Tuple( int i, String s, String t) {
        index = i;
        source = s;
        target = t;
    }
}

class MyTupleComparator implements Comparator<Tuple> {
    public int compare(Tuple a, Tuple b) {
        return a.index - b.index;
    }
}

Solution 2:
O(n) solution. Use hash map to store the indexes to be replaced.

Code (Java):

class Solution {
    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < indexes.length; i++) {
            map.put(indexes[i], i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            if (map.containsKey(i)) {
                int index = map.get(i);
                String source = sources[index];
                String target = targets[index];
                
                if (i + source.length() <= S.length() && 
                    S.substring(i, i + source.length()).equals(source)) {
                    sb.append(target);
                    i += source.length() - 1;
                } else {
                    sb.append(S.charAt(i));
                }
            } else {
                sb.append(S.charAt(i));
            }
        }

        return sb.toString();
    }
}