列表

详情


KS29. 查找无重复最长子串

描述

给定一个字符串,请找出其中长度最长且不含有重复字符的子串,计算该子串长度。

数据范围:输入的字符串长度满足 ,字符串中仅包含小写的英文字母

输入描述

输入类型为字符串,例如”abcde“

输出描述

输出类型为整型, 例如 5

示例1

输入:

pwwkew

输出:

3

说明:

无重复字符的最长子串是"kew",其长度为 3

原站题解

C 解法, 执行用时: 4ms, 内存消耗: 384KB, 提交时间: 2022-01-13

#include <stdio.h>
#include <assert.h>
#define MAXpo 100001
#define MAX 100000
int main(void)
{
    char test_ch;
    while((test_ch = getchar()) != EOF)
    {
        ungetc(test_ch, stdin);
        char s[MAXpo], ch;   int idx = 0;
        while((ch = getchar())!='\n' && idx<MAX)
        {
            assert(ch>='a' && ch<='z');
            s[ idx++ ] = ch;
        }
        assert(ch=='\n' && idx<=MAX);   s[idx] = '\n';
        
        int i = 0, j, max = 0, val;
        char record[26] = {0};
        for(j=0; j<idx; j++){
            if( !record[ s[j]-'a' ] ){ record[ s[j]-'a' ] = 1;   continue; }
            if(j-i > max) max = j-i;
            ch = s[j];
            for( ; s[i]!=ch; i++) record[ s[i]-'a' ] = 0;
            i++;
        }
        printf("%d\n", idx-i > max ? idx-i : max);
    }
    return 0;
}

Go 解法, 执行用时: 5ms, 内存消耗: 1108KB, 提交时间: 2022-07-07

package main

import (
	"fmt"
	"io/ioutil"
	"os"
	"strings"
)

func scan() string {
	rowsBytes, _ := ioutil.ReadAll(os.Stdin)
	//rowsBytes := []byte("pwwkew")
	rows := strings.Split(string(rowsBytes), "\n")
	return rows[0]
}

func main() {
	s := scan()
	sLen := len(s)
	maxLen := 1
	currentLen := 1
	for i := 1; i < sLen; i++ {
		j := i - 1
		for ; j >= i-currentLen; j-- {
			if s[j] == s[i] {
				break
			}
		}
		currentLen = i - j
		if maxLen < currentLen {
			maxLen = currentLen
		}
	}
	fmt.Println(maxLen)
}

上一题