首页 > 试题广场 >

最长不含重复字符的子字符串

[编程题]最长不含重复字符的子字符串
  • 热度指数：55606 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围:

示例1

输入

"abcabcbb"

输出

3

说明

因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例2

输入

"bbbbb"

输出

1

说明

因为无重复字符的最长子串是"b"，所以其长度为 1。
示例3

输入

"pwwkew"

输出

3

说明

因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
算法知识视频讲解
添加回答
C
零零七007_多孝子版头像 零零七007_多孝子版
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
#include <string.h>
int lengthOfLongestSubstring(char* s ) {
    // write code here
    int sample[129] = {0}, maxlen = 0, templen = 0, k = 1;
    for (int i = 0; i <= strlen(s); i++) {
        if (sample[s[i]] == 0 && i != strlen(s)) {
            sample[s[i]] = k++;
        } else {
            if (maxlen < k - 1)maxlen = k - 1;
            k -= sample[s[i]];
            templen = sample[s[i]];
            for (int j = 0; j < 129; j++) {
                if (sample[j] > 0)sample[j] -= templen;
                if (sample[j] < 0)sample[j] = 0;
            }
            sample[s[i]] = k++;
        }
    }

    return maxlen;
}
发表于 2024-04-28 09:43:48 回复(0)
C
小小小孩头像 小小小孩 
#define MAX_LEN 40000
int lengthOfLongestSubstring(char* s ) {
    // write code here
    char buf[MAX_LEN] = {0};
    int i = 0,ret =0,tmp=0;
    int len = strlen(s);
    while(i<len)
    {
        tmp = 0;
        int l = i,j;
        while(i<len && buf[s[i]]==0)
        {
            buf[s[i]]++;
            tmp++;
            i++;
        }
        if(i<len && buf[s[i]]>0)
        {
            ret = ret>tmp?ret:tmp;
            memset(buf,0,MAX_LEN);
            for(j=l;j<i;j++)
            {
                if(s[j]==s[i])
                    break;
            }
            i = j+1;
        }
    }
      return  ret>tmp?ret:tmp;
}

发表于 2023-06-12 14:50:41 回复(0)
C
方堃KroosKun头像 方堃KroosKun
C语言做法 简单移动 用数组代替哈希表 不过思想是类似的
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
 */
#include <string.h>
#define max(x,y)((x)>(y)?(x):(y))

int lengthOfLongestSubstring(char* s ) {
    // write code here
    int len = strlen(s);
    //appear数组类似于哈希表 appear[s[i]]存放每个字符出现过的次数
    //s[i]是字符 如abcab s[0]==s[3]=='a'
    //不难发现 appear[s[0]]==appear[s[3]]==appear['a']
    int appear[10000] = {0};
    //ans保存最大长度
    int ans = 0;
    //i和j是不含重复字符的子字符串的首尾指针
    for (int i=0, j=0; j<len; j++) {
        //尾指针j开始扫描 字符出现就次数+1
        appear[s[j]]++;
        //存在重复出现的字符
        //如abcab appear[s[0]]==appear[s[3]]==appear[a]
        while (i<j && appear[s[j]]>1) {
            //重复出现的字符 出现次数-1
            appear[s[i]]--;
            //首指针i向后移动一位
            i++;
        }
        //ans取ans和每次子串长度的最大值
        ans = max(ans, j-i+1);
    }
    return ans;
}


发表于 2023-03-04 09:37:03 回复(0)
C
李顺利plus头像 李顺利plus
高时间复杂度的无脑解法 
int lengthOfLongestSubstring(char* s ) {
    // write code here
    int max=0;
    for(int i=0;s[i]!='\0';i++){
        int sum=1;
        for(int j=i+1;s[j]!='\0';j++){
            int si=0;
            for(int k=j-1;k>=i;k--){
                if(s[k]==s[j]) si=1;
            }
            if(si==1) break;
            else sum++;
        }
        if(sum>max) max=sum;
    }
    return max;
}

发表于 2022-10-08 16:47:17 回复(0)
提交观点

问题信息

字符串 哈希 双指针
难度：
4条回答 11024浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长不含重复字符的子字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号