原题:
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc". For "bbbbb" the longest substring is "b".
思路:
可以顺序遍历字符串,并将字符出现的位置记录到一个hash表中。假设遍历到字符i,发现之前有重复的字符(但要在当前最子字符串的范围内,比如tmmzuxt,第二个 t 就不会和第一个 t 重复),可以从hash表中获取之前重复字符的位置p,那么字符串i可以和p后面的字符串组成新的子字符串(即当前子字符串),持续这个过程知道遍历完整个字符串,并记录期间出现过的最长的字符串。
由于是字符,但要存储位置,所以可以采用一个int型长度为128的数组来代替hash表。
代码如下:
public static void lengthOfLongestSubstring(String s){
//表示asc码位置。
int[] hash = new int[128];
//最长无重复子字符串的起始位置
int lcStart = 0;
//最长无重复子字符串的长度。
int lcLen = 0;
//当前无重复字符串的其实位置。
int clcStart = 0;
int len = s.length();
for(int i=0;i<len;i++){
char c = s.charAt(i);
int index = hash[c];
hash[c] = i + 1;
if(index > 0 && index > clcStart){
clcStart = index;
}else{
int clen = (i + 1) - clcStart;
if(clen > lcLen){
lcLen = clen;
lcStart = clcStart;
}
}
}
System.out.println("start=" + lcStart + ",len=" + lcLen);
System.out.println("LSWRC of ["+s+"] is ["+s.substring(lcStart, lcStart+lcLen)+"]");
}
分享到:
相关推荐
在字符串中找到最长的不包含重复字符的子串,返回其长度
C语言编程-编写函数fun求一个字符串的长度,在main函数中输入字符串,并输出其长度;
Python编程题--回文字符串
⼤⼀python基础编程题-基本编程题--python 基本编程题 --python 1、让Python帮你随机选⼀个饮品吧! import random listC = ["加多宝", "雪碧", "可乐", "勇闯天涯", "椰⼦汁"] print(random.choices(listC), type...
第一讲-常用类编程-数组-字符串和集合.ppt
腾讯2011年10月15日校招笔试算法编程题
精彩编程与编程技巧-将文件大小变成相应的字符串 ...
在一个已知的字符串中查找最长单词,假定字符串中只含字母和空格,空格用来分隔不同单词。(C语言)
C语言编程-编写一个函数,该函数可以统计一个长度为2的字符串在另一个字符串中出现的次数;
Linux运维-操作系统 教程 从入门到精通101课-80-82脚本编程-字符串.mp4
精彩编程与编程技巧-加密字符串算法 ...
将包含有Null结尾的字符串转换为VB字符串
精彩编程与编程技巧-清除字符串中指定的字符 ...
找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad" 主要用的是矩阵的思想
精彩编程与编程技巧-在文本框中快速增加一串字符 ...
精彩编程与编程技巧-翻转一个字符串 ...
Excel-VBA宏编程实例源代码-由剪贴版中获取文本字符串.zip
Linux运维-3.Shell编程-12 shell编程-133字符串处理之排序、取消重复行、统计.avi