Skip to content

2213. Longest Substring of One Repeating Character

  • Time: $O(n\log n)$
  • Space: $O(n)$
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
struct SegmentTreeNode {
  int lo;
  int hi;
  char maxChar;
  char prefixChar;
  char suffixChar;
  int maxLength;
  int prefixLength;
  int suffixLength;
  SegmentTreeNode* left;
  SegmentTreeNode* right;
  SegmentTreeNode(int lo, int hi, char maxChar, char prefixChar,
                  char suffixChar, int maxLength, int prefixLength,
                  int suffixLength, SegmentTreeNode* left = nullptr,
                  SegmentTreeNode* right = nullptr)
      : lo(lo),
        hi(hi),
        maxChar(maxChar),
        prefixChar(prefixChar),
        suffixChar(suffixChar),
        maxLength(maxLength),
        prefixLength(prefixLength),
        suffixLength(suffixLength),
        left(left),
        right(right) {}
  ~SegmentTreeNode() {
    delete left;
    delete right;
    left = nullptr;
    right = nullptr;
  }
};

class SegmentTree {
 public:
  SegmentTree(const string& s) : root(build(s, 0, s.length() - 1)) {}
  ~SegmentTree() {
    delete root;
  }

  void update(int i, char val) {
    root = update(root, i, val);
  }

  int getMaxLength() {
    return root->maxLength;
  }

 private:
  SegmentTreeNode* root;

  SegmentTreeNode* build(const string& s, int lo, int hi) const {
    if (lo == hi)
      return new SegmentTreeNode(lo, hi, s[lo], s[lo], s[lo], 1, 1, 1);
    const int mid = (lo + hi) / 2;
    SegmentTreeNode* left = build(s, lo, mid);
    SegmentTreeNode* right = build(s, mid + 1, hi);
    return merge(left, right);
  }

  SegmentTreeNode* update(SegmentTreeNode* root, int i, char c) {
    if (root->lo == i && root->hi == i) {
      root->maxChar = c;
      root->prefixChar = c;
      root->suffixChar = c;
      return root;
    }
    const int mid = (root->lo + root->hi) / 2;
    if (i <= mid) {
      SegmentTreeNode* updatedLeft = update(root->left, i, c);
      return root = merge(updatedLeft, root->right);
    } else {
      SegmentTreeNode* updatedRight = update(root->right, i, c);
      return root = merge(root->left, updatedRight);
    }
  }

  SegmentTreeNode* merge(SegmentTreeNode* left, SegmentTreeNode* right) const {
    // Get maxChar and maxLength
    char maxChar = ' ';
    int maxLength = 0;
    if (left->maxLength > right->maxLength) {
      maxChar = left->maxChar;
      maxLength = left->maxLength;
    } else {
      maxChar = right->maxChar;
      maxLength = right->maxLength;
    }
    if (left->suffixChar == right->prefixChar &&
        left->suffixLength + right->prefixLength > maxLength) {
      maxChar = left->suffixChar;
      maxLength = left->suffixLength + right->prefixLength;
    }

    // Get prefixChar and prefixLength
    char prefixChar = left->prefixChar;
    int prefixLength = left->prefixLength;
    if (left->lo + prefixLength == right->lo &&
        left->prefixChar == right->prefixChar)
      prefixLength += right->prefixLength;

    // Get suffixChar and suffixLength
    char suffixChar = right->suffixChar;
    int suffixLength = right->suffixLength;
    if (right->hi - suffixLength == left->hi &&
        right->suffixChar == left->suffixChar)
      suffixLength += left->suffixLength;

    return new SegmentTreeNode(left->lo, right->hi, maxChar, prefixChar,
                               suffixChar, maxLength, prefixLength,
                               suffixLength, left, right);
  }
};

class Solution {
 public:
  vector<int> longestRepeating(string s, string queryCharacters,
                               vector<int>& queryIndices) {
    vector<int> ans;
    SegmentTree tree(s);

    for (int i = 0; i < queryIndices.size(); ++i) {
      tree.update(queryIndices[i], queryCharacters[i]);
      ans.push_back(tree.getMaxLength());
    }

    return ans;
  }
};