专栏首页眯眯眼猫头鹰的小树杈395. Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters

题目要求

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

找出字符串中的最长子字符串,满足该子字符串中任何字符出现的次数都大于k。

思路和代码

这是一个经典的分治法解决的问题,关键在于我们如何将这个问题分解为更小的子问题。反过来想,这个子字符串一定不包含什么元素呢?当一个元素出现的总次数小于k,那么该元素一定不在子字符串中,只需要将其作为分界点,分别找出左半部分和右半部分的满足条件的最长子字符串。

    public int longestSubstring(String s, int k) {
        return longestSubstring(s, k, 0, s.length()-1);
    }
    
    public int longestSubstring(String s, int k, int left, int right) {
        if(left > right) {
            return 0;
        }

        int[] count = new int[26];
        for(int i = left ; i<=right ; i++) {
            count[s.charAt(i) - 'a']++;
        }
        int result = right - left + 1;
        for(int i = left ; i<=right ; i++) {
            if(count[s.charAt(i)-'a'] < k && count[s.charAt(i)-'a'] > 0) {
                int leftLongest = longestSubstring(s, k, left, i-1);
                int rightLongest = longestSubstring(s, k, i+1, right);
                result = Math.max(leftLongest, rightLongest);
                
                break;
            }
        }
        return result;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode363. Max Sum of Rectangle No Larger Than K

    现有一个由整数构成的矩阵,问从中找到一个子矩阵,要求该子矩阵中各个元素的和为不超过k的最大值,问子矩阵中元素的和为多少? 注:后面的文章中将使用[左上角顶点坐标...

    眯眯眼的猫头鹰
  • 547. Friend Circles

    There are N students in a class. Some of them are friends, while some are not. T...

    眯眯眼的猫头鹰
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • P1983 车站分级

    题目描述 一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一...

    attack
  • cf1000F. One Occurrence(线段树 set)

    首先把询问离线,预处理每个数的\(pre, nxt\),同时线段树维护\(pre\)(下标是\(pre\),值是\(i\)),同时维护一下最大值

    attack
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • Hebuter Daily Training 201810

    有三个人Y,W,D.每个人都很想去一个地方.但是不好请假.所以能去一个 地方就很好了.Y想出来一个方法.每个人掷骰子.点数最多的赢.就可以去 他想去的地方.Y,...

    xiaohejun
  • Lake Counting (POJ No.2386)

    题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

    杨鹏伟
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • P2419 [USACO08JAN]牛大赛Cow Contest

    题目背景 [Usaco2008 Jan] 题目描述 N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are ...

    attack

扫码关注云+社区

领取腾讯云代金券