java - 如何找到包含两个唯一重复字符的最长子字符串

Question

任务是找出给定字符串中由任意两个唯一重复字符组成的最长子字符串
前任。在输入字符串“aabadefghaabbaagad”中，最长的字符串是“aabbaa”

我提出了以下解决方案，但想看看是否有更有效的方法来做到这一点

import java.util.*; 

public class SubString {
    public static void main(String[] args) { 
    //String inStr="defghgadaaaaabaababbbbbbd";
    String inStr="aabadefghaabbaagad";
    //String inStr="aaaaaaaaaaaaaaaaaaaa";
    System.out.println("Input string is         "+inStr);

    StringBuilder sb = new StringBuilder(inStr.length());
    String subStr="";
    String interStr="";
    String maxStr="";
    int start=0,length=0, maxStart=0, maxlength=0, temp=0;

    while(start+2<inStr.length())   
    {    int i=0;
         temp=start;
         char x = inStr.charAt(start);
         char y = inStr.charAt(start+1);
         sb.append(x);
         sb.append(y);

         while( (x==y) && (start+2<inStr.length()) )
         {    start++;
              y = inStr.charAt(start+1);
              sb.append(y);
         }

         subStr=inStr.substring(start+2);
         while(i<subStr.length())
         {    if(subStr.charAt(i)==x || subStr.charAt(i)==y )
              {    sb.append(subStr.charAt(i));
                   i++;
              }
              else
                   break;
         }

         interStr= sb.toString();
         System.out.println("Intermediate string "+ interStr);
         length=interStr.length();
         if(maxlength<length)
         {    maxlength=length;
              length=0;
              maxStr = new String(interStr);
              maxStart=temp;
         }

         start++;
         sb.setLength(0);
   }

   System.out.println("");
   System.out.println("Longest string is "+maxStr.length()+" chars long "+maxStr);  
}
}

Answer 1

这里有一个提示，可能会引导您使用线性时间算法(我假设这是家庭作业，所以我不会给出完整的解决方案):在您找到一个既不等于 x 或 y，没有必要一直返回到 start + 1 并重新开始搜索。让我们以字符串 aabaaddaa 为例。当您看到 aabaa 并且下一个字符是 d 时，没有必要在索引 1 或 2 重新开始搜索，因为在那些情况下，您在再次点击 d 之前，您只会得到 abaa 或 baa。事实上，您可以将 start 直接移动到索引 3(最后一组 a 的第一个索引)，并且由于您已经知道有一个a 到 d 的连续序列，您可以将 i 移动到索引 5 并继续。

编辑:下面的伪代码。

// Find the first letter that is not equal to the first one, 
// or return the entire string if it consists of one type of characters
int start = 0;
int i = 1;
while (i < str.length() && str[i] == str[start])
    i++;
if (i == str.length())
    return str;

// The main algorithm
char[2] chars = {str[start], str[i]};
int lastGroupStart = 0;
while (i < str.length()) {
    if (str[i] == chars[0] || str[i] == chars[1]) {
        if (str[i] != str[i - 1])
            lastGroupStart = i;
    }
    else {
        //TODO: str.substring(start, i) is a locally maximal string; 
        //      compare it to the longest one so far
        start = lastGroupStart;
        lastGroupStart = i;
        chars[0] = str[start];
        chars[1] = str[lastGroupStart];
    }
    i++;
}
//TODO: After the loop, str.substring(start, str.length()) 
//      is also a potential solution.