KS29. 查找无重复最长子串
描述
输入描述
输入类型为字符串,例如”abcde“输出描述
输出类型为整型, 例如 5示例1
输入:
pwwkew
输出:
3
说明:
无重复字符的最长子串是"kew",其长度为 3C 解法, 执行用时: 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) }