【线段树】2213. 由单个字符重复的最长子字符串-阿里云开发者社区

算法可以发掘本质，如：

一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。

二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。

三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。

四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。

一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。而这三者是等效问题。

本文涉及知识点

线段树

LeetCode 2213. 由单个字符重复的最长子字符串

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数下标数组 queryIndices ，这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询之后 s 中仅由单个字符重复组成的最长子字符串的长度。

示例 1：

输入：s = “babacc”, queryCharacters = “bcb”, queryIndices = [1,3,3]

输出：[3,3,4]

解释：

第 1 次查询更新后 s = “bbbacc” 。由单个字符重复组成的最长子字符串是 “bbb” ，长度为 3 。
第 2 次查询更新后 s = “bbbccc” 。由单个字符重复组成的最长子字符串是 “bbb” 或 “ccc”，长度为 3 。
第 3 次查询更新后 s = “bbbbcc” 。由单个字符重复组成的最长子字符串是 “bbbb” ，长度为 4 。
因此，返回 [3,3,4] 。
示例 2：

输入：s = “abyzz”, queryCharacters = “aa”, queryIndices = [2,1]

输出：[2,3]

解释：

第 1 次查询更新后 s = “abazz” 。由单个字符重复组成的最长子字符串是 “zz” ，长度为 2 。
第 2 次查询更新后 s = “aaazz” 。由单个字符重复组成的最长子字符串是 “aaa” ，长度为 3 。
因此，返回 [2,3] 。

提示：

1 <= s.length <= 10⁵

s 由小写英文字母组成

k == queryCharacters.length == queryIndices.length

1 <= k <= 10⁵

queryCharacters 由小写英文字母组成

0 <= queryIndices[i] < s.length

用向量实现的线段树

template<class TSave>
class CVectorSave
{
public:
  CVectorSave(int iMinIndex,int iMaxIndex, TSave tDefault) :m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex){
    m_vec.assign((iMaxIndex-iMinIndex+1)*4, tDefault);
  }
  TSave& Ref(int iNodeNO) {
    return m_vec[iNodeNO];
  }
  const int m_iMinIndex, m_iMaxIndex;
protected:
  vector<TSave> m_vec;
};
template<class TSave, class TRecord,class TSaveCon = CVectorSave<TSave> >
class CSingUpdateLineTree
{
public:
  CSingUpdateLineTree(int iEleSize, TSave tDefault) :m_vSave(0,iEleSize-1, tDefault){
  }
  CSingUpdateLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) :m_vSave(iMinIndex, iMaxIndex, tDefault) {
  }
  void Update(int index, TRecord update) {
    Update(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, index, update);
  }
  void Query(int leftIndex, int leftRight) {
    Query(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, leftIndex, leftRight);
  }
  void Init() {
    Init(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex);
  }
  TSave QueryAll() {
    return m_vSave.Ref(1);
  }
protected:
  void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  {
    if (iSaveLeft == iSaveRight) {
      OnInit(m_vSave.Ref(iNodeNO), iSaveLeft);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    Init(iNodeNO * 2, iSaveLeft, mid);
    Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
    OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
  }
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
    if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
      OnQuery(m_vSave.Ref(iNodeNO));
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
    if (iSaveLeft == iSaveRight)
    {
      OnUpdate(m_vSave.Ref(iNodeNO), iSaveLeft, update);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iUpdateNO <= mid) {
      Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
    }
    else {
      Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
    }
    OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
  }
  virtual void OnInit(TSave& save, int iSave) = 0;
  virtual void OnQuery(TSave& save) = 0;
  virtual void OnUpdate(TSave& save,int iSaveLeft, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
  CVectorSave<TSave> m_vSave;
};
template<class TSave = std::tuple<int,int,int>, class TRecord = char, class TSaveCon = CVectorSave<TSave> >
class CMyLineTree :public CSingUpdateLineTree<TSave,TRecord>
{
public:
  CMyLineTree(const string& s) :m_s(s), CSingUpdateLineTree<TSave, TRecord>(s.length(), { 0,0,0 }) {
  }
  void Update(int index, TRecord update) {
    m_s[index] = update;
    CSingUpdateLineTree<TSave, TRecord>::Update(index, update);
  }
protected:
  virtual void OnInit(TSave& save, int iSave) override
  {
    save = { 1,1,1 };
  }
  virtual void OnQuery(TSave& save) override
  {
  }
  virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
  {
    save = { 1,1,1 };
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
  {
    int i1 = get<0>(left);//最长前缀
    int i2 = max(get<1>(left), get<1>(r));//最长字符串
    int i3 = get<2>(r);//最长后缀
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (m_s[mid] == m_s[mid + 1])
    {//拼接
      i2 = max(i2, get<2>(left) + get<0>(r));
      if (mid - iSaveLeft + 1 == i1) {
        i1 += get<0>(r);
      }
      if (iSaveRight - mid == i3) {
        i3 += get<2>(left);
      }
    }
    par = { i1,i2,i3 };
  }
   string m_s;
};
class Solution {
public:
  vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
    CMyLineTree lineTree(s);
    lineTree.Init();
    vector<int> vRet;
    for (int i = 0; i < queryCharacters.size(); i++) {
      lineTree.Update(queryIndices[i], queryCharacters[i]);
      const auto [i1, i2, i3] = lineTree.QueryAll();
      vRet.emplace_back(i2);
    }
    return vRet;
  }
};

用哈希映射实现

template<class TSave>
class CUnorderMapSave
{
public:
  CUnorderMapSave(int iMinIndex, int iMaxIndex, TSave tDefault) :m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex), m_tDefault(tDefault){  
  }
  TSave& Ref(int iNodeNO) {
    if (!m_map.count(iNodeNO)) {
      m_map[iNodeNO] = m_tDefault;
    }
    return m_map[iNodeNO];
  }
  const int m_iMinIndex, m_iMaxIndex;
protected:
  const TSave m_tDefault;
  unordered_map<int, TSave> m_map;
};
template<class TSave, class TRecord,class TSaveCon >
class CSingUpdateLineTree
{
public:
  CSingUpdateLineTree(int iEleSize, TSave tDefault) :m_vSave(0,iEleSize-1, tDefault){
  }
  CSingUpdateLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) :m_vSave(iMinIndex, iMaxIndex, tDefault) {
  }
  void Update(int index, TRecord update) {
    Update(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, index, update);
  }
  void Query(int leftIndex, int leftRight) {
    Query(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, leftIndex, leftRight);
  }
  void Init() {
    Init(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex);
  }
  TSave QueryAll() {
    return m_vSave.Ref(1);
  }
protected:
  void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  {
    if (iSaveLeft == iSaveRight) {
      OnInit(m_vSave.Ref(iNodeNO), iSaveLeft);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    Init(iNodeNO * 2, iSaveLeft, mid);
    Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
    OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
  }
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
    if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
      OnQuery(m_vSave.Ref(iNodeNO));
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
    if (iSaveLeft == iSaveRight)
    {
      OnUpdate(m_vSave.Ref(iNodeNO), iSaveLeft, update);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iUpdateNO <= mid) {
      Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
    }
    else {
      Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
    }
    OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
  }
  virtual void OnInit(TSave& save, int iSave) = 0;
  virtual void OnQuery(TSave& save) = 0;
  virtual void OnUpdate(TSave& save,int iSaveLeft, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
  TSaveCon m_vSave;
};
template<class TSave = std::tuple<int,int,int>, class TRecord = char, class TSaveCon = CUnorderMapSave<TSave> >
class CMyLineTree :public CSingUpdateLineTree<TSave,TRecord, TSaveCon>
{
public:
  CMyLineTree(const string& s) :m_s(s), CSingUpdateLineTree<TSave, TRecord, TSaveCon>(s.length() ,{ 0,0,0 }) {
  }
  void Update(int index, TRecord update) {
    m_s[index] = update;
    CSingUpdateLineTree<TSave, TRecord, TSaveCon>::Update(index, update);
  }
protected:
  virtual void OnInit(TSave& save, int iSave) override
  {
    save = { 1,1,1 };
  }
  virtual void OnQuery(TSave& save) override
  {
  }
  virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
  {
    save = { 1,1,1 };
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
  {
    int i1 = get<0>(left);//最长前缀
    int i2 = max(get<1>(left), get<1>(r));//最长字符串
    int i3 = get<2>(r);//最长后缀
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (m_s[mid] == m_s[mid + 1])
    {//拼接
      i2 = max(i2, get<2>(left) + get<0>(r));
      if (mid - iSaveLeft + 1 == i1) {
        i1 += get<0>(r);
      }
      if (iSaveRight - mid == i3) {
        i3 += get<2>(left);
      }
    }
    par = { i1,i2,i3 };
  }
   string m_s;
};
class Solution {
public:
  vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
    CMyLineTree lineTree(s);
    lineTree.Init();
    vector<int> vRet;
    for (int i = 0; i < queryCharacters.size(); i++) {
      lineTree.Update(queryIndices[i], queryCharacters[i]);
      const auto [i1, i2, i3] = lineTree.QueryAll();
      vRet.emplace_back(i2);
    }
    return vRet;
  }
};

再次修改封装类

template<class TSave, class TRecord >
class CSingUpdateLineTree
{
protected:
  virtual void OnInit(TSave& save, int iSave) = 0;
  virtual void OnQuery(TSave& save) = 0;
  virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) = 0;
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};
template<class TSave, class TRecord >
class CVectorSingUpdateLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:
  CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize),m_vSave(iEleSize*4,tDefault){
  }
  void Update(int index, TRecord update) {
    Update(1, 0, m_iEleSize-1, index, update);
  }
  void Query(int leftIndex, int leftRight) {
    Query(1, 0, m_iEleSize - 1, leftIndex, leftRight);
  }
  void Init() {
    Init(1, 0, m_iEleSize - 1);
  }
  TSave QueryAll() {
    return m_vSave[1];
  }
protected:
  int m_iEleSize;
  void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
  {
    if (iSaveLeft == iSaveRight) {
      this->OnInit(m_vSave[iNodeNO], iSaveLeft);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    Init(iNodeNO * 2, iSaveLeft, mid);
    Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
    this->OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO*2], m_vSave[iNodeNO*2+1], iSaveLeft, iSaveRight);
  }
  void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
    if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
      this->OnQuery(m_vSave[iNodeNO]);
      return;
    }
    if (iSaveLeft == iSaveRight) {//没有子节点
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (mid >= iQueryLeft) {
      Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
    }
    if (mid + 1 <= iQueryRight) {
      Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
    }
  }
  void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
    if (iSaveLeft == iSaveRight)
    {
      this->OnUpdate(m_vSave[iNodeNO], iSaveLeft, update);
      return;
    }
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (iUpdateNO <= mid) {
      Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
    }
    else {
      Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
    }
    this->OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO*2], m_vSave[iNodeNO*2+1], iSaveLeft, iSaveRight);
  }
  vector<TSave> m_vSave;
};
template<class TSave = std::tuple<int, int, int>, class TRecord = char >
class CMyLineTree :public CVectorSingUpdateLineTree<TSave, TRecord>
{
public:
  CMyLineTree(const string& s) :m_s(s), CVectorSingUpdateLineTree<TSave, TRecord>(s.length(), { 0,0,0 }) {
  }
  void Update(int index, TRecord update) {
    m_s[index] = update;
    CVectorSingUpdateLineTree<TSave, TRecord>::Update(index, update);
  }
protected:
  
  string m_s;
  virtual void OnInit(TSave& save, int iSave) override
  {
    save = { 1,1,1 };
  }
  virtual void OnQuery(TSave& save) override
  {
  }
  virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
  {
    save = { 1,1,1 };
  }
  virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
  {
    int i1 = get<0>(left);//最长前缀
    int i2 = max(get<1>(left), get<1>(r));//最长字符串
    int i3 = get<2>(r);//最长后缀
    const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
    if (m_s[mid] == m_s[mid + 1])
    {//拼接
      i2 = max(i2, get<2>(left) + get<0>(r));
      if (mid - iSaveLeft + 1 == i1) {
        i1 += get<0>(r);
      }
      if (iSaveRight - mid == i3) {
        i3 += get<2>(left);
      }
    }
    par = { i1,i2,i3 };
  }
};
class Solution {
public:
  vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
    CMyLineTree lineTree(s);
    lineTree.Init();
    vector<int> vRet;
    for (int i = 0; i < queryCharacters.size(); i++) {
      lineTree.Update(queryIndices[i], queryCharacters[i]);
      const auto [i1, i2, i3] = lineTree.QueryAll();
      vRet.emplace_back(i2);
    }
    return vRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  string s,  queryCharacters;
  vector<int> queryIndices;
  {
    s = "babacc", queryCharacters = "bcb", queryIndices = {1,3,3};
    auto res = Solution().longestRepeating(s, queryCharacters, queryIndices);
    Assert({ 3,3,4 }, res);
  }
  {
    s = "abyzz", queryCharacters = "aa", queryIndices = { 2, 1 };
    auto res = Solution().longestRepeating(s, queryCharacters, queryIndices);
    Assert({ 2,3 }, res);
  }
  //CConsole::Out(res);
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【线段树】2213. 由单个字符重复的最长子字符串