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

Each replacement operation has3parameters: a starting indexi, a source word x and a target word y. The rule is that ifx starts at positioni in theoriginalstringS, 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 position2 in the original stringS, we will replace it with"ffff".

Using another example onS = "abcd", if we have both the replacement operationi = 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.

class Solution {
    private class Combo{
        int index;
        String source;
        String target;

        public Combo(int index, String source, String target){
            this.index = index;
            this.source = source;
            this.target = target;
        }
    }

    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        if (S == null || indexes.length == 0) return S;

        List<Combo> list = new ArrayList<>();
        for (int i = 0; i < indexes.length; i++){
            list.add(new Combo(indexes[i], sources[i], targets[i]));
        }

        Collections.sort(list, (a, b) -> (a.index - b.index));

        StringBuilder sb = new StringBuilder();
        int tracker = 0, index = 0;
        while (tracker < S.length()){
            if (index >= list.size() || tracker < list.get(index).index){
                sb.append(S.charAt(tracker));
                tracker++;
            }
            else if (tracker == list.get(index).index){
                int end = tracker + list.get(index).source.length();
                String wordInS = S.substring(tracker, end);

                if (wordInS.equals(list.get(index).source)){
                    sb.append(list.get(index).target);
                    tracker = end;
                    index++;
                }
                else{
                    sb.append(wordInS);
                    tracker = end;
                    index++;
                }
            }

        }

        return sb.toString();
    }
}