首先,子串是连续的序列,不连续的不是字串,其次是不含重复元素。
例如,字符串:abcdcefg 显然最大字串是:dcefg
该解法的思想是依次遍历字符串,在另一个数组保存该字符串出现的索引位,通过索引位可得到当前遍历的字串的长度。当字符重复出现的时候,减去之前相同字符出现的索引,便可得到此时字符串长度。每次遍历保存最大字符串长度,在出现重复字符时进行比较更新。
代码如下:
package com.practice;
import java.util.HashMap;
import java.util.Map;
public class GetMaxStr {
public static int getStr(String str) {
if(str.length()==0) return 0;
Map<Character, Integer> map = new HashMap<Character, Integer>();
int[] lengthArr = new int[str.length()];
lengthArr[0] = 1;
map.put(str.charAt(0), 0);
int maxLength = 1;
for(int i=1; i<str.length(); i++) {
Character c = str.charAt(i);
if(map.containsKey(c)) {
lengthArr[i] = i - map.get(c);
maxLength = Math.max(maxLength, lengthArr[i]);
}else {
lengthArr[i] = lengthArr[i-1] + 1;
maxLength = lengthArr[i];
map.put(c, i);
}
}
return maxLength;
}
public static void main(String[] args) {
String str = "aab";
System.out.println(getStr(str));
}
}
测试结果是:2, 即ab
分享到:
相关推荐
两个字符串中最大相同的子串。 "qwerabcdtyuiop" "xcabcdvbn
C++实现找出两个字符串中最大的公共子串
找出一个字符串中出现次数最多的子字符串,并返回重复次数。使用java编写
在字符串中找到最长的不包含重复字符的子串,返回其长度
该文件实现了在两个字符串中寻找最大子串的算法,并附上代码,方便大家学习。
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串为“local...
编写程序求出所给出的字符串中最长的字母子串(以非字母隔开)。例如字符串"Apple$12pear watermelon $ # Banana"中最长的字母子串为"watermelon"。有详细的解释
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
在随意给出的2个字符串中,找出它们共同的最长的子串。 【输入】 输入文件的第一行为一个整数2,接下来有2行,每行为一个字符串,每个字符串的长度均小于255。 【输出】 输出只有一行,即:共同的最长子串,若有多个...
# 给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。 # 如果存在,则输出YES,否则输出NO。 # 回文串的定义:记串str逆序之后的字符串是str1,若str=str1,则称str是回文串,如"abcba". # 输入...
输入母串以及子串开始偏移地址和结束偏移地址,成功返回获取到的子串,失败返回空串
找出一个字符串的最长子串,很简单.......
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3.
在字符串中查找最长重复子串的探讨 写一个函数,找出一个字符串中最长的重复子串。“t1t1”结果就是t1."cabcabca"结果就是cab或者abc或者bca。
在一个字符串s中查找有几个字串subs,结果返回字串的个数。主要用的indexOf()函数。
找出两个字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串为"cad" 主要用的是矩阵的思想
有两个字符串A,B,判断B是不是A的子串
此程序为VC6.0实现判断一个字符串是否为另一个字符串的子串
自己闲来没事写的字符串删除,事件复杂度为 n 欢迎大家讨论