Longest Substring of One Repeating Character LeetCode solution in Java

1
class Solution {
2
  class TreeNode {
3
    // range
4
    int start;
5
    int end;
6

7
    // conti left char
8
    char leftChar;
9
    int leftCharLen;
10

11
    // conti right char
12
    char rightChar;
13
    int rightCharLen;
14

15
    int max;
16

17
    TreeNode left;
18
    TreeNode right;
19

20
    TreeNode(int start, int end) {
21
      this.start = start;
22
      this.end = end;
23
      left = null;
24
      right = null;
25
    }
26
  }
27

28
  public int[] longestRepeating(String s, String queryCharacters, int[] queryIndices) {
29
    char[] sChar = s.toCharArray();
30
    char[] qChar = queryCharacters.toCharArray();
31

32
    TreeNode root = buildTree(sChar, 0, sChar.length - 1);
33

34
    int[] result = new int[qChar.length];
35

36
    for (int i = 0; i < qChar.length; i++) {
37
      updateTree(root, queryIndices[i], qChar[i]);
38
      result[i] = root.max;
39
    }
40
    return result;
41
  }
42

43
  private TreeNode buildTree(char[] s, int from, int to) {
44
    if (from > to) return null;
45
    TreeNode root = new TreeNode(from, to);
46
    if (from == to) {
47
      root.max = 1;
48
      root.rightChar = root.leftChar = s[from];
49
      root.leftCharLen = root.rightCharLen = 1;
50
      return root;
51
    }
52

53
    int middle = from + (to - from) / 2;
54

55
    root.left = buildTree(s, from, middle);
56
    root.right = buildTree(s, middle + 1, to);
57

58
    updateNode(root);
59
    return root;
60
  }
61

62
  private void updateTree(TreeNode root, int index, char c) {
63
    if (root == null || root.start > index || root.end < index) {
64
      return;
65
    }
66
    if (root.start == index && root.end == index) {
67
      root.leftChar = root.rightChar = c;
68
      return;
69
    }
70
    updateTree(root.left, index, c);
71
    updateTree(root.right, index, c);
72

73
    updateNode(root);
74
  }
75

76
  private void updateNode(TreeNode root) {
77
    if (root == null) return;
78
    root.leftChar = root.left.leftChar;
79
    root.leftCharLen = root.left.leftCharLen;
80
    root.rightChar = root.right.rightChar;
81
    root.rightCharLen = root.right.rightCharLen;
82
    root.max = Math.max(root.left.max, root.right.max);
83
    if (root.left.rightChar == root.right.leftChar) {
84
      int len = root.left.rightCharLen + root.right.leftCharLen;
85
      if (root.left.leftChar == root.left.rightChar
86
          && root.left.leftCharLen == root.left.end - root.left.start + 1) {
87
        root.leftCharLen = len;
88
      }
89
      if (root.right.leftChar == root.right.rightChar
90
          && root.right.leftCharLen == root.right.end - root.right.start + 1) {
91
        root.rightCharLen = len;
92
      }
93
      root.max = Math.max(root.max, len);
94
    }
95
  }
96
}