Go Java算法之K个重复字符最长子串详解

目录
  • 至少有K个重复字符的最长子串
  • 方法一:分治(Java)
  • 方法二:滑动窗口(go)

至少有K个重复字符的最长子串

给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

  • 示例 1:

输入:s = "aaabb", k = 3

输出:3

解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次。

  • 示例 2:

输入:s = "ababbc", k = 2

输出:5

解释:最长子串为 "ababb" ,其中 'a' 重复了 2 次, 'b' 重复了 3 次。

方法一:分治(Java)

对于字符串 s,如果存在某个字符 ch,它的出现次数大于 0 且小于 k,则任何包含 ch 的子串都不可能满足要求。

也就是说,我们将字符串按照 ch 切分成若干段,则满足要求的最长子串一定出现在某个被切分的段内,而不能跨越一个或多个段。

具体思路:

  • 先整体考虑,如果某个字符在整个字符串中的出现次数 < k,那它一定不会出现在合法子串中。
  • s: aaabbaa,k: 3,b 只出现 2 次,它肯定不会出现在合法子串中,要到它的两侧找。
  • 考察aaa和aa,变成一个规模较小的子问题,递归去求aaa和aa中合法子串的最长长度。
  • 当递归到子问题的规模足够小,即,子串的长度小于 k,即便子串的字符都相同,字符的出现次数也小于 k,所以没有合法子串,返回 0
class Solution {
   public int longestSubstring(String s, int k) {
       int n = s.length();
       return dfs(s, 0, n - 1, k);
   }
   public int dfs(String s, int l, int r, int k) {
       int[] cnt = new int[26];
       for (int i = l; i <= r; i++) {
           cnt[s.charAt(i) - 'a']++;
       }
       char split = 0;
       for (int i = 0; i < 26; i++) {
           if (cnt[i] > 0 && cnt[i] < k) {
               split = (char) (i + 'a');
               break;
           }
       }
       if (split == 0) {
           return r - l + 1;
       }
       int i = l;
       int ret = 0;
       while (i <= r) {
           while (i <= r && s.charAt(i) == split) {
               i++;
           }
           if (i > r) {
               break;
           }
           int start = i;
           while (i <= r && s.charAt(i) != split) {
               i++;
           }
           int length = dfs(s, start, i - 1, k);
           ret = Math.max(ret, length);
       }
       return ret;
   }
}

N:为字符串的长度

Σ 为字符集

时间复杂度:O(N⋅∣Σ∣)

空间复杂度:O(∣Σ∣^2)

方法二:滑动窗口(go)

对于给定的字符种类数量 t,我们维护滑动窗口的左右边界 l,r 滑动窗口内部每个字符出现的次数 cnt,以及滑动窗口内的字符种类数目 total。

当 total>t 时,我们不断地右移左边界 l,并对应地更新 cnt 以及 total,直到 total≤t 为止。这样,对于任何一个右边界 r,我们都能找到最小的 l(记为 l_{min}),使得 s[l_{min}...r]之间的字符种类数目不多于 t。

通过维护额外的计数器 less,我们无需遍历 cnt 数组,就能知道每个字符是否都出现了至少 k 次,同时可以在每次循环时,在常数时间内更新计数器的取值。

func longestSubstring(s string, k int) (ans int) {
   for t := 1; t <= 26; t++ {
       cnt := [26]int{}
       total := 0
       lessK := 0
       l := 0
       for r, ch := range s {
           ch -= 'a'
           if cnt[ch] == 0 {
               total++
               lessK++
           }
           cnt[ch]++
           if cnt[ch] == k {
               lessK--
           }
           for total > t {
               ch := s[l] - 'a'
               if cnt[ch] == k {
                   lessK++
               }
               cnt[ch]--
               if cnt[ch] == 0 {
                   total--
                   lessK--
               }
               l++
           }
           if lessK == 0 {
               ans = max(ans, r-l+1)
           }
       }
   }
   return ans
}
func max(a, b int) int {
   if a > b {
       return a
   }
   return b
}

N:为字符串的长度

Σ 为字符集

时间复杂度:O(N⋅∣Σ∣+∣Σ∣^2)

空间复杂度:O(∣Σ∣)

以上就是Go Java算法之K个重复字符最长子串详解的详细内容,更多关于Go Java算法重复字符子串的资料请关注我们其它相关文章!

(0)

相关推荐

  • Go Java算法之找不同示例详解

    目录 找不同 方法一:计数(Java) 方法二:求和(Go) 找不同 给定两个字符串 s 和 t ,它们只包含小写字母. 字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母. 请找出在 t 中被添加的字母. 示例 1: 输入:s = "abcd", t = "abcde" 输出:"e" 解释:'e' 是那个被添加的字母. 示例 2: 输入:s = "", t = "y" 输出:"y&q

  • Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go Java算法之字符串中第一个唯一字符详解

    目录 字符串中第一个唯一字符 方法一:哈希表(Java) 方法二:队列(Go) 字符串中第一个唯一字符 给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 .如果不存在,则返回 -1 . 示例 1: 输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 提示: 1 <= s.length <= 10

  • Go Java算法之简化路径实例详解

    目录 简化路径 方法一:栈(Java) 方法二:标准库(Go) 简化路径 给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径. 在 Unix 风格的文件系统中,一个点(.)表示当前目录本身:此外,两个点 (..) 表示将目录切换到上一级(指向父目录):两者都可以是复杂相对路径的组成部分. 任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' . 对于此问题,任何其他格式的点(例如,'...')均被视为文件/

  • Go Java 算法之字符串解码示例详解

    目录 字符串解码 方法一:栈(Java) 方法二:递归(Go) 字符串解码 给定一个经过编码的字符串,返回它解码后的字符串. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正重复 k 次.注意 k 保证为正整数. 你可以认为输入字符串总是有效的:输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的. 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入. 示例 1: 输入:

  • Go java 算法之括号生成示例详解

    目录 括号生成 方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=

  • Go Java算法之K个重复字符最长子串详解

    目录 至少有K个重复字符的最长子串 方法一:分治(Java) 方法二:滑动窗口(go) 至少有K个重复字符的最长子串 给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k .返回这一子串的长度. 示例 1: 输入:s = "aaabb", k = 3 输出:3 解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次. 示例 2: 输入:s = "ababbc", k = 2 输出:5

  • Java文件(io)编程之文件字符流使用方法详解

    本文实例为大家分享了文件字符流的使用方法,供大家参考,具体内容如下 案例1: 读取一个文件并写入到另一个文件中,char[] 来中转. 首先要在E盘下创建一个文本文档,命名为test.txt,输入一些字符串. public class Demo_5 { public static void main(String[] args) { FileReader fr=null; //文件取出字符流对象(输入流) FileWriter fw=null; //写入到文件(输出流) try { fr=new

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • Java IO流之字符流的使用详解

    目录 一.字符流的出现 二.字符输入流Reader 三.文件字符输入流 FileReader 四.字符输出流 Writer 五.文件字符输出流 FileWriter 六.close()和flush()的区别 七.换行和续写 八.使用try-catch-finally处理流异常 一.字符流的出现 中文在GBK中占有两个字节,在utf-8中占有三个字节(即需要三个字节才能组成一个中文字),字节流读取中文时由于编码集的不同,字节流读取中文也比较麻烦,从而出现了字符流 字符流也在java.io包下 二.

  • Java多线程之显示锁和内置锁总结详解

    总结多线程之显示锁和内置锁 Java中具有通过Synchronized实现的内置锁,和ReentrantLock实现的显示锁,这两种锁各有各的好处,算是互有补充,这篇文章就是做一个总结. *Synchronized* 内置锁获得锁和释放锁是隐式的,进入synchronized修饰的代码就获得锁,走出相应的代码就释放锁. synchronized(list){ //获得锁 list.append(); list.count(); }//释放锁 通信 与Synchronized配套使用的通信方法通常

  • java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • java数组的三种扩容方式以及程序实现详解

    因为数组是在内存中连续的一段存储空间,所以数组一旦被创建,空间就固定了,长度是不能扩增的. 数组的长度是固定的,如果需要扩充**,必须创建新数组,原数组的长度要复制到新数组中 .** java中,数组类型的变量传值的时候,事实上传递的是数组的地址 . Java数组扩容的原理 1)Java数组对象的大小是固定不变的,数组对象是不可扩容的. 2)利用数组复制方法可以变通的实现数组扩容. 3)System.arraycopy()可以复制数组. 4)Arrays.copyOf()可以简便的创建数组副本.

  • java数据结构图论霍夫曼树及其编码示例详解

    目录 霍夫曼树 一.基本介绍 二.霍夫曼树几个重要概念和举例说明  构成霍夫曼树的步骤 霍夫曼编码 一.基本介绍 二.原理剖析 注意: 霍夫曼编码压缩文件注意事项 霍夫曼树 一.基本介绍 二.霍夫曼树几个重要概念和举例说明  构成霍夫曼树的步骤 举例:以arr = {1  3  6  7  8   13   29}  public class HuffmanTree { public static void main(String[] args) { int[] arr = { 13, 7, 8

  • Java 通过手写分布式雪花SnowFlake生成ID方法详解

    目录 SnowFlake算法 SnowFlake优点: SnowFlake算法 SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图: 分为四段: 第一段: 1位为未使用,永远固定为0. (因为二进制中最高位是符号位,1表示负数,0表示正数.生成的id一般都是用正整数,所以最高位固定为0 ) 第二段: 41位为毫秒级时间(41位的长度可以使用69年) 第三段: 10位为workerId(10位的长度最多支持部署1024个节点) (这里的10位又分为两部分,第一部分5位表

  • Java 通过手写分布式雪花SnowFlake生成ID方法详解

    目录 SnowFlake算法 SnowFlake优点 SnowFlake不足 SnowFlake算法 SnowFlake算法生成id的结果是一个64bit大小的整数,它的结构如下图: 分为四段: 第一段: 1位为未使用,永远固定为0. (因为二进制中最高位是符号位,1表示负数,0表示正数.生成的id一般都是用正整数,所以最高位固定为0 ) 第二段: 41位为毫秒级时间(41位的长度可以使用69年) 第三段: 10位为workerId(10位的长度最多支持部署1024个节点) (这里的10位又分为

随机推荐