【离散差分】LeetCode2953:统计完全子字符串

简介: 【离散差分】LeetCode2953:统计完全子字符串

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本题其它解法

【滑动窗口】LeetCode2953:统计完全子字符串

涉及知识点

分块循环 离散差分

题目

给你一个字符串 word 和一个整数 k 。

如果 word 的一个子字符串 s 满足以下条件,我们称它是 完全字符串:

s 中每个字符 恰好 出现 k 次。

相邻字符在字母表中的顺序 至多 相差 2 。也就是说,s 中两个相邻字符 c1 和 c2 ,它们在字母表中的位置相差 至多 为 2 。

请你返回 word 中 完全 子字符串的数目。

子字符串 指的是一个字符串中一段连续 非空 的字符序列。

示例 1:

输入:word = “igigee”, k = 2

输出:3

解释:完全子字符串需要满足每个字符恰好出现 2 次,且相邻字符相差至多为 2 :igigee, igigee, igigee 。

示例 2:

输入:word = “aaabbbccc”, k = 3

输出:6

解释:完全子字符串需要满足每个字符恰好出现 3 次,且相邻字符相差至多为 2 :aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc, aaabbbccc 。

参数范围

1 <= word.length <= 105

word 只包含小写英文字母。

1 <= k <= word.length

解法一:离散化差分

分块循环处理条件二

我们可以将word拆分若干字串,相邻字符相差超过2时拆分。

变量解析

vIndex 记录26个字母的索引
mDiff 差分有序映射,记录那些索引是合法的完全字串的开始。合法范围必须是26个字母合法,每个字母的合法范围是:每有此字母或有k个此字母。

时间复杂度

O(nm1logm2),n是字符串的长度,m1是字母数,m2是mDiff的长度,不超过26*4。超时

代码

核心代码

class Solution {
public:
int countCompleteSubstrings(string word, int k) {
m_iK = k;
int pre = 0;
int iRet = 0;
for (int i = 0; i < word.length(); i++)
{
if (i && (abs(word[i] - word[i - 1]) > 2))
{
iRet += Do(word.substr(pre, i - pre));
pre = i ;
}
}
iRet += Do(word.substr(pre, word.length()));
return iRet;
}
int Do(const string& s)
{
int iRet = 0;
vector<vector> vIndex(26, vector(1, -1));
for (int i = 0 ; i < s.length();i++ )
{
const auto& ch = s[i];
vIndex[ch - ‘a’].emplace_back(i);
iRet += GetNum(vIndex,i);
std::cout << “i " << i << " iRet:” << iRet << std::endl;
}
return iRet;
}
int GetNum(const vector<vector>& vIndex,int cur)
{
std::map<int, int> mDiff;
for (int j = 0; j < 26; j++)
{
const auto& v = vIndex[j];
//不选择字母’a’+j
mDiff[v.back()+1]++;
mDiff[cur+1]–;
//选择k个字母
if (v.size() > m_iK )
{
//左开右闭空间
const int iMin = v[v.size() - m_iK-1];
const int iMax = v[v.size() - m_iK ];
mDiff[iMin+1]++;
mDiff[iMax+1]–;
}
}
int iCnt = 0;
int iRet = 0;
for ( auto it = mDiff.begin(); it != mDiff.end(); ++it )
{
iCnt += it->second;
if (26 == iCnt)
{
iRet += std::next(it)->first - it->first;
}
}
return iRet;
}
int m_iK;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
string s;
int k, res;
{
Solution slu;
s = “gvgvvgv”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(1, res);
}
{
Solution slu;
s = “igigee”;
k = 2;
auto res = slu.countCompleteSubstrings(s, k);
Assert(3, res);
}
{
Solution slu;
s = “aaabbbccc”;
k = 3;
auto res = slu.countCompleteSubstrings(s, k);
Assert(6, res);
}
//CConsole::Out(res);

}

优化

一,mDiff 不用每次都重写处理,只处理当前字母的变化。

二,vIndex 第一维用原生数组。

优化后代码

class Solution {
public:
  int countCompleteSubstrings(string word, int k) {
    m_iK = k;
    int pre = 0;
    int iRet = 0;
    for (int i = 0; i < word.length(); i++)
    {
      if (i && (abs(word[i] - word[i - 1]) > 2))
      {
        iRet += Do(word.substr(pre, i - pre));
        pre = i;
      }
    }
    iRet += Do(word.substr(pre, word.length()));
    return iRet;
  }
  int Do(const string& s)
  {
    for (int i = 0; i < 26; i++)
    {
      if( vIndex[i].empty())
      {
        vIndex[i].emplace_back(-1);
      }
      else if(vIndex[i].size() > 1)
      {
        vIndex[i].erase(vIndex[i].begin() + 1, vIndex[i].end());
      }
    }
    int iRet = 0;
    std::map<int, int> mDiff;   
    mDiff[0] = 26;
    for (int i = 0; i < s.length(); i++)
    {
      vector<int>& v = vIndex[s[i] - 'a'];
      Change(v, mDiff, -1);
      v.emplace_back(i);
      Change(v, mDiff, 1);
      iRet += GetNum(mDiff,i);
    }
    return iRet;
  }
  void Add(std::map<int, int>& mDiff, const int index, int iChange = 1)
  {
    mDiff[index] += iChange;
    if (0 == mDiff[index])
    {
      mDiff.erase(index);
    }
  }
  void Change(const vector<int>& v, std::map<int, int>& mDiff, int iAdd )
  {
    Add(mDiff,v.back()+1, iAdd);
    if (v.size() > m_iK)
    {
      const int iMin = v[v.size() - m_iK - 1];
      const int iMax = v[v.size() - m_iK];
      Add(mDiff, iMin + 1, iAdd);
      Add(mDiff, iMax + 1, -iAdd);
    }
  }
  int GetNum(std::map<int, int>& mDiff,int cur)
  {
    int iCnt = 0;
    int iRet = 0;
    for (auto it = mDiff.begin(); it != mDiff.end(); ++it)
    {
      iCnt += it->second;
      if (26 == iCnt)
      {
        const auto itNext = std::next(it);
        iRet +=  (( mDiff.end() == itNext) ? cur+1 :  std::next(it)->first) - it->first;
      }
    }
    return iRet;
  }
  vector<int> vIndex[26];
  int m_iK;
};


。也就是我们常说的专业的人做专业的事。 |

|如果程序是一条龙,那算法就是他的是睛|

测试环境

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

或者 操作系统:win10 开发环境:

VS2022 C++17

相关文章
|
12天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
存储 算法
LeetCode第43题字符串相乘
LeetCode第43题"字符串相乘"的解题方法,通过使用数组存储乘积并处理进位,避免了字符串转换数字的复杂性,提高了算法效率。
LeetCode第43题字符串相乘
|
2月前
|
算法 Java
LeetCode第28题找出字符串中第一个匹配项的下标
这篇文章介绍了LeetCode第28题"找出字符串中第一个匹配项的下标"的两种解法:暴力解法和KMP算法,并解释了KMP算法通过构建前缀表来提高字符串搜索的效率。
LeetCode第28题找出字符串中第一个匹配项的下标
|
2月前
|
算法
LeetCode第8题字符串转换整数 (atoi)
该文章介绍了 LeetCode 第 8 题字符串转换整数 (atoi)的解法,需要对字符串进行格式解析与校验,去除前导空格和处理正负号,通过从高位到低位的计算方式将字符串转换为整数,并处理越界情况。同时总结了这几道题都需要对数字的表示有理解。
LeetCode第8题字符串转换整数 (atoi)
|
2月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
22 0
|
4月前
|
算法
力扣每日一题 6/23 字符串/模拟
力扣每日一题 6/23 字符串/模拟
33 1
|
3月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
4月前
|
索引
力扣每日一题 6/27 字符串 贪心
力扣每日一题 6/27 字符串 贪心
27 0
|
4月前
|
Python
力扣随机一题 模拟+字符串
力扣随机一题 模拟+字符串
26 0
|
4月前
力扣每日一题 6/22 字符串/贪心
力扣每日一题 6/22 字符串/贪心
24 0