Largest Merge Of Two Strings LeetCode solution in Java

1
class Solution {
2
  public String largestMerge(String word1, String word2) {
3
    StringBuilder sb = new StringBuilder();
4
    int i = 0;
5
    int j = 0;
6
    char[] w1 = word1.toCharArray();
7
    char[] w2 = word2.toCharArray();
8

9
    int n1 = w1.length;
10
    int n2 = w2.length;
11

12
    // we loop until we exhaust any one of the 2 words completely
13
    while (i < n1 && j < n2) {
14

15
      // if both the characters are equal we choose the one where the next largest occurs earlier
16
      if (w1[i] == w2[j]) {
17
        if (check(w1, i, w2, j)) {
18
          sb.append(w1[i++]);
19
        } else {
20
          sb.append(w2[j++]);
21
        }
22
      }
23

24
      // else we greedily choose the largest of the two characters
25
      else if (w1[i] > w2[j]) {
26
        sb.append(w1[i++]);
27
      } else {
28
        sb.append(w2[j++]);
29
      }
30
    }
31

32
    // at the end of the loop we append any remaining word
33
    sb.append(word1.substring(i));
34
    sb.append(word2.substring(j));
35

36
    return sb.toString();
37
  }
38

39
  private boolean check(char[] w1, int i, char[] w2, int j) {
40
    // will return true if we need to extract from word1 and false if we need to extract from word2
41

42
    while (i < w1.length && j < w2.length) {
43
      if (w1[i] == w2[j]) {
44
        i++;
45
        j++;
46
      } else if (w1[i] > w2[j]) {
47
        return true;
48
      } else {
49
        return false;
50
      }
51
    }
52

53
    // if we are unable to find any exhaustable character till the end of the loop we use the one
54
    // having larger length
55
    if (i < w1.length) {
56
      return true;
57
    }
58
    return false;
59
  }
60
}