h****n
发帖数: 1093 | 1 比如
abcbcbcbcbcddd 返回bcbcbcbcbc
abbbcccbbbcccd 返回bbbcccbbbccc
看了以前的一些帖子，说是用两个指针夹起来做，能做到O（n）
不过具体细节怎么也想不明白，请指教，如果有具体的code学习就更好了
多谢 |
s**x
发帖数: 7506 | 2 Frequency counter for each characters,
One Counter cc for total unique char.
Scan from left to right
increase counter for that char
If this counter is 1, increase cc;
If cc == 2, record a candidate;
If cc== 3 {
Move left side till we get cc == 2;
Cc-- if one char freq is 0.
} |
h****n
发帖数: 1093 | 3
----------------这个地方不好check啊，怎么check till cc==2？
【在 s**x 的大作中提到】
: Frequency counter for each characters,
: One Counter cc for total unique char.
: Scan from left to right
: increase counter for that char
: If this counter is 1, increase cc;
: If cc == 2, record a candidate;
: If cc== 3 {
: Move left side till we get cc == 2;
: Cc-- if one char freq is 0.
: }
|
h****n
发帖数: 1093 | 4 我明白了，你是要维护一个int counter[256].. |
s**x
发帖数: 7506 | 5
对，要是全是小写，26就够了，要是大字母表就用hash table 。
这个跟minimum covering window 实际上是一样的。
【在 h****n 的大作中提到】
: 我明白了，你是要维护一个int counter[256]..
|
s******7
发帖数: 1758 | 6 我给你写个java的
这种前后双指针夹逼得淫荡招数一定要用熟练
public static String findLongest(String s)
{
int max=0;
int maxRight=0;
int maxLeft=0;
char c1=s.charAt(0);
int last1=0; //record last c1 position
char c2=' ';
int n=s.length();
int j=0; //后指针
for (int i=1; i
{
if(s.charAt(i)==c1||s.charAt(i)==c2)
{
if(s.charAt(i)==c1) last1=i;
if(i-j>max)
{
max=i-j;
maxRight=i;
maxLeft=j;
}
}
else
{
c1=c2;
c2=s.charAt(i);
j=last1+1; //后指针上前夹逼
}
}
return s.substring(maxLeft, maxRight+1);
}
test:
System.out.println(findLongest("abcbcbcbcbcddd"));
System.out.println(findLongest("abbbcccbbbcccd"));
bcbcbcbcbc
bbbcccbbbccc |
h****n
发帖数: 1093 | 7 牛逼的紧，我根据大牛的思路写了个C++的
string longestSubstringWithTwoUniqueCharacters(string S)
{
string res;
int letterCount[256];
int uniqueCount = 0;
int len = S.size();
int begin=0, end=0, maxLen = 0;
memset(letterCount,0,256*sizeof(int));
for(begin=0,end=0;end
{
letterCount[(int)S[end]]++;
if(letterCount[(int)S[end]]==1) uniqueCount++;
if(uniqueCount==2)
{
if(maxLen < end-begin+1)
{
maxLen = end-begin+1;
res = S.substr(begin, maxLen);
}
}
else if(uniqueCount>2)
{
while(uniqueCount>2)
{
letterCount[(int)S[begin]]--;
if(letterCount[(int)S[begin]]==0) uniqueCount--;
begin++;
}
}
}
return res;
}
【在 s**x 的大作中提到】
:
: 对，要是全是小写，26就够了，要是大字母表就用hash table 。
: 这个跟minimum covering window 实际上是一样的。
|
s**x
发帖数: 7506 | 8 差不多，那个decrease unique count 的地方也应该check == 2 的case I think.
You can Rearrange code a little bit, to avoid duplicated code.
【在 h****n 的大作中提到】
: 牛逼的紧，我根据大牛的思路写了个C++的
: string longestSubstringWithTwoUniqueCharacters(string S)
: {
: string res;
: int letterCount[256];
: int uniqueCount = 0;
: int len = S.size();
: int begin=0, end=0, maxLen = 0;
: memset(letterCount,0,256*sizeof(int));
:
|
h****n
发帖数: 1093 | 9 那里应该不用，因为一旦uniquecount大于2就会立即进入那个减成2的过程，也就是说
uniquecount不会大于3，只能是变成3然后减1变成2
多谢大牛指点
【在 s**x 的大作中提到】
: 差不多，那个decrease unique count 的地方也应该check == 2 的case I think.
: You can Rearrange code a little bit, to avoid duplicated code.
|
s**x
发帖数: 7506 | 10 嗯， 想了想即使 check 了， 也应该不会大于已有的 candidate. 俺不牛, 喜欢抛砖
引玉而已。
【在 h****n 的大作中提到】
: 那里应该不用，因为一旦uniquecount大于2就会立即进入那个减成2的过程，也就是说
: uniquecount不会大于3，只能是变成3然后减1变成2
: 多谢大牛指点
|
|
|
b*******g
发帖数: 57 | 11 我觉得得考虑一下corner case吧，比如aaaaaaaaaa |
b*******g
发帖数: 57 | 12 贴个用hashmap的
string longestSubstrTwoUnique(string s) {
string longestSubstr;
int maxLen = 0;
unordered_map hashmap;
for (int begin = 0, end = 0; end < s.size(); ++end) {
++hashmap[s[end]];
if (hashmap.size() <= 2) {
if (maxLen < end-begin+1) {
maxLen = end-begin+1;
longestSubstr = s.substr(begin,maxLen);
}
}
while (hashmap.size() > 2) {
if (--hashmap[s[begin]] == 0)
hashmap.erase(s[begin]);
++begin;
}
}
return longestSubstr;
} |
w********s
发帖数: 1570 | 13 #include
#include
int max_length(std::string str)
{
int length = str.length();
if (length <= 1) return length;
int dict[26] = {0};
int i = 0;
int count = 1;
int max_length = 1;
dict[str[0] - 'a'] = 1;
for (int j = 1; j < length; ++j)
{
char c = str[j];
if (dict[c - 'a'] > 0)
{
++max_length;
}
else
{
++count;
dict[c - 'a'] = 1;
if (count > 2)
{
// erase the head char
char p = str[i];
dict[str[i] - 'a'] = 0;
while (str[i] == p) ++i;
int length = j - i + 1;
if (length > max_length) max_length = length;
count--;
}
else
{
++max_length;
}
}
}
return max_length;
}
int main(int argc, char* argv[])
{
std::string s(argv[1]);
int l = max_length(s);
std::cout << l << "\n";
return 0;
} |
J*****a
发帖数: 4262 | 14 写个java的
public String twoDistinct(String input){
if(input == null) return null;
String rl = "";
int[] count = new int[256];
for(int s = 0, distinct = 0, i = 0; i < input.length(); i++){
if(count[input.charAt(i)]++ == 0) distinct++;
if(distinct == 2 && rl.length() < i - s + 1)
rl = input.substring(s, i+1);
if(distinct > 2){
while(--count[input.charAt(s++)] != 0);
distinct--;
}
}
return rl;
} |
P**********k
发帖数: 1629 | 15 void find_longest_substring(string str, int n, int& start_best, int& end_
best){
string pool (2, ' ');
int pool_size = 0;
int start, shift, end;
char cur;
int length_max=0, length_cur;
start=0;
pool[0]=str[start];
pool_size++;
for(int i=1; i
if(str[i]!=str[i-1]){
cur = str[i];
if(pool_size<2 && pool[0]!= cur){
pool[pool_size] = cur;
pool_size++;
shift = i;
continue;
}
if (pool_size == 2){
if (!in_pool(pool, pool_size, cur)){
end = i-1;
length_cur = end-start+1;
if (length_cur>length_max){
length_max = length_cur;
start_best = start;
end_best = end;
}
start = shift;
}
// pop up the older character, push back the newer character
pool[0] = pool[1];
pool[1] = cur;
}
shift = i;
}
}
end = n-1;
length_cur = end-start+1;
if(length_cur>length_max){
start_best = start;
end_best = end;
}
} |
e****b
发帖数: 25 | 16 呃 问下什么叫做 contains just tw.... 没看懂题
谢了 |
P**********k
发帖数: 1629 | 17 substring里面只有两个unique的字符，比如只含有 a,b
【在 e****b 的大作中提到】
: 呃 问下什么叫做 contains just tw.... 没看懂题
: 谢了
|
s******7
发帖数: 1758 | 18 这道题其实不用记录a,b出现的count, 只要记录最后一个a出现的位置，只要unique
count>2的时候， left pointer直接跳到那个记录的位置就可以了，不用一个一个走上
去，详细见我的的code。虽然都是O(n)，但是效率应该能高点。 |
f********5
发帖数: 4 | 19 贡献一个python的，行数少看起来有一种莫名的爽...
def substrWithDistinctWords(s, k):
n = len(s)
if n <= k: return s #string with length less than k always passes
front, rear, h, substr = 0, 0, {}, ''
while front < n:
h[s[front]] = h.get(s[front],0) + 1
if len(h.keys()) <= 2:
if len(substr) < front-rear+1:
substr = s[rear:front+1]
front += 1
while len(h.keys()) > 2:
tmpChar = s[rear]
rear += 1
h[tmpChar] -= 1
if h[tmpChar] == 0: h.pop(tmpChar)
return substr |
k*****L
发帖数: 55 | 20 abbbbbaaaaaccccccccccccccccccccc?
【在 s******7 的大作中提到】
: 我给你写个java的
: 这种前后双指针夹逼得淫荡招数一定要用熟练
: public static String findLongest(String s)
: {
: int max=0;
: int maxRight=0;
: int maxLeft=0;
: char c1=s.charAt(0);
: int last1=0; //record last c1 position
: char c2=' ';
|
|
|
s******7
发帖数: 1758 | 21 对，写得疏忽了，应该考虑最后出现的可能是last1， 也可能是last2,然后后指针再直
接跳到这个位置，更新最后出现的字符。
上面的code更正了，多谢指点
【在 k*****L 的大作中提到】
: abbbbbaaaaaccccccccccccccccccccc?
|
f*******4
发帖数: 64 | 22 曾写过这个题
int longest2chars(const string &s) {
int b=0, f=-1, ans=0, N=s.size(); // b:seq_start; f:end of the 1st char
for (int i=1; i
if (f>=0 && s[i] != s[f]) {
ans = max(ans, i-b);
b = f+1;
}
f = i-1;
}
return max(ans, N-b);
} |
b*******e
发帖数: 217 | 23 string findLongestSubStr(string A) {
int maxLen = -1;
int 1stIdx = 0;
int 2ndIdx = -1;
int 3rdIdx = -1;
int max1stIdx = -1;
int max3rdIdx = -1;
int i = 0;
while (i < A.size()) {
if (1stIdx == 0 && A[i] == A[1stIdx]) {
i++;
continue;
}
if (2ndIdx < 0) {
2ndIdx = i;
}
if (2ndIdx >= 0 && A[i] == A[2ndIdx]) {
i++;
continue;
}
3ndIdx = i;
currLen = 3rdIdx - 1stIdx;
if (currLen > maxLen) {
max1stIdx = 1stIdx;
max3rdIdx = 3rdIdx;
}
maxLen = std::max(currLen, maxLen);
1stIdx = 2ndIdx;
2ndIdx = 3ndIdx;
i++;
}
if (max3rdIdx >= 0 && max1stIdx >= 0) {
return A.substr(max1stIdx, maxLen);
}
return string();
} |
