395. Longest Substring with At Least K Repeating Characters

給定字符串s和整數k,找出s中的最長子串,要求子串中的每一字符出現的次數都不少于k鹰服,返回這一子串的長度。

思路有點難理解

參考 https://github.com/ShusenTang/LeetCode/blob/master/solutions/395.%20Longest%20Substring%20with%20At%20Least%20K%20Repeating%20Characters.md

題目中先定了字符串中只有26個小寫字母,滿足題意的子串中不同字母數在1-26范圍內悲酷,從1-26枚舉套菜,對于每個cnt,維護窗口指針start和end设易,不斷更新start和end逗柴,保持窗口內不同字符數不超過cnt,用一個大小為26的數組來記錄窗口內每個字母的出現次數顿肺。

更新start和end方式戏溺,讓end不斷加1更新,start的更新看情況:
判斷end是不是一個全新的字符屠尊,是的情況下讓uniquecnt加1旷祸,這個時候可能uniquecnt超過了指定的cnt,需要將start右移直到 uniquecnt 不超過 cnt讼昆,每次更新好end和start后還需要判斷窗口內每個字符串是否滿足條件托享,若是應該嘗試更新 res

  • 時間復雜度 O(26 * n + 26^2),空間復雜度O(26)
  • Runtime: 134 ms, faster than 45.31%
  • Memory Usage: 41 MB, less than 75.00%
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstring = function(s, k) {
  let res = 0;
  const len = s.length;
  for (let i = 1; i <= 26; i++) {
    let left = 0;
    let right = 0;
    let unique = 0;
    const count = new Array(26).fill(0);
    while (right < len) {
      if (count[s[right].charCodeAt() - 97]++ === 0) {
        unique++;
      }
      while (unique > i) {
        if (--count[s[left++].charCodeAt() - 97] === 0) {
          unique--;
        }
      }
      
      let valid = true;
      for (let item of count) {
        if (item > 0 && item < k) {
          valid = false;
          break;
        }
      }
      if (valid) {
        res = Math.max(res, right - left + 1);
      }
      right++;
    }
  }
  return res;
};
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末浸赫,一起剝皮案震驚了整個濱河市闰围,隨后出現的幾起案子,更是在濱河造成了極大的恐慌既峡,老刑警劉巖羡榴,帶你破解...
    沈念sama閱讀 207,248評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現場離奇詭異运敢,居然都是意外死亡校仑,警方通過查閱死者的電腦和手機,發(fā)現死者居然都...
    沈念sama閱讀 88,681評論 2 381
  • 文/潘曉璐 我一進店門者冤,熙熙樓的掌柜王于貴愁眉苦臉地迎上來肤视,“玉大人,你說我怎么就攤上這事「” “怎么了?”我有些...
    開封第一講書人閱讀 153,443評論 0 344
  • 文/不壞的土叔 我叫張陵乐纸,是天一觀的道長。 經常有香客問我汽绢,道長吗跋,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 55,475評論 1 279
  • 正文 為了忘掉前任,我火速辦了婚禮酗宋,結果婚禮上,老公的妹妹穿的比我還像新娘蜕猫。我一直安慰自己,他們只是感情好哎迄,可當我...
    茶點故事閱讀 64,458評論 5 374
  • 文/花漫 我一把揭開白布回右。 她就那樣靜靜地躺著,像睡著了一般漱挚。 火紅的嫁衣襯著肌膚如雪翔烁。 梳的紋絲不亂的頭發(fā)上旨涝,一...
    開封第一講書人閱讀 49,185評論 1 284
  • 那天,我揣著相機與錄音颊糜,去河邊找鬼。 笑死衬鱼,一個胖子當著我的面吹牛,可吹牛的內容都是我干的蒜胖。 我是一名探鬼主播,決...
    沈念sama閱讀 38,451評論 3 401
  • 文/蒼蘭香墨 我猛地睜開眼台谢,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了朋沮?” 一聲冷哼從身側響起缀壤,我...
    開封第一講書人閱讀 37,112評論 0 261
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎塘慕,沒想到半個月后,有當地人在樹林里發(fā)現了一具尸體图呢,經...
    沈念sama閱讀 43,609評論 1 300
  • 正文 獨居荒郊野嶺守林人離奇死亡骗随,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 36,083評論 2 325
  • 正文 我和宋清朗相戀三年鸿染,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片牡昆。...
    茶點故事閱讀 38,163評論 1 334
  • 序言:一個原本活蹦亂跳的男人離奇死亡摊欠,死狀恐怖丢烘,靈堂內的尸體忽然破棺而出些椒,到底是詐尸還是另有隱情播瞳,我是刑警寧澤免糕,帶...
    沈念sama閱讀 33,803評論 4 323
  • 正文 年R本政府宣布,位于F島的核電站牌芋,受9級特大地震影響,放射性物質發(fā)生泄漏躺屁。R本人自食惡果不足惜经宏,卻給世界環(huán)境...
    茶點故事閱讀 39,357評論 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望烁兰。 院中可真熱鬧,春花似錦沪斟、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,357評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至朱巨,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背必峰。 一陣腳步聲響...
    開封第一講書人閱讀 31,590評論 1 261
  • 我被黑心中介騙來泰國打工钻蹬, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人问欠。 一個月前我還...
    沈念sama閱讀 45,636評論 2 355
  • 正文 我出身青樓,卻偏偏與公主長得像顺献,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子注整,可洞房花燭夜當晚...
    茶點故事閱讀 42,925評論 2 344

推薦閱讀更多精彩內容