Как найти самую длинную подстроку, содержащую два уникальных повторяющихся символа

Question

Задача состоит в том, чтобы найти самую длинную подстроку в заданной строке, которая состоит из любых двух уникальных повторяющихся символов
Ex. во входной строке «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, потому что в этих случаях вы получите только abaa или baa, прежде чем снова нажать d. На самом деле, вы можете переместить start прямо в индекс 3 (первый индекс последней группы a s), и поскольку вы уже знаете, что существует непрерывная секвенция a s до d, вы можете переместить i в индекс 5 и продолжить.

Редактировать: Pseudocode ниже.

// 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. 

Answer 2

так, как я думать об этом, чтобы решить эту проблему в 2 этапа

• сканировать всю строку, чтобы найти непрерывные потоки одной и той же буквы
• петли извлеченные сегменты и не сконденсировать их до тех пор, u получить пробел.

Таким образом, вы можете также изменить логику для сканирования самой длинной подстроки произвольной длины не только 2.

class Program 
{ 

    static void Main(string[] args)  
    { 
     //.   
     string input = "aabbccdddxxxxxxxxxxxxxxxxx"; 
     int max_chars = 2; 

     //. 
     int flip = 0; 

     var scanned = new List<string>(); 

     while (flip > -1) 
     { 
      scanned.Add(Scan(input, flip, ref flip)); 
     } 

     string found = string.Empty; 
     for(int i=0;i<scanned.Count;i++) 
     { 
      var s = Condense(scanned, i, max_chars); 
      if (s.Length > found.Length) 
      { 
       found = s; 
      } 
     } 

     System.Console.WriteLine("Found:" + found); 
     System.Console.ReadLine(); 


    } 

    /// <summary> 
    /// 
    /// </summary> 
    /// <param name="s"></param> 
    /// <param name="start"></param> 
    /// <returns></returns> 
    private static string Scan(string s, int start, ref int flip) 
    { 
     StringBuilder sb = new StringBuilder(); 

     flip = -1; 

     sb.Append(s[start]); 

     for (int i = start+1; i < s.Length; i++) 
     { 
      if (s[i] == s[i - 1]) { sb.Append(s[i]); continue; } else { flip=i; break;} 
     } 

     return sb.ToString(); 
    } 

    /// <summary> 
    /// 
    /// </summary> 
    /// <param name="list"></param> 
    /// <param name="start"></param> 
    /// <param name="repeat"></param> 
    /// <param name="flip"></param> 
    /// <returns></returns> 
    private static string Condense(List<string> list, int start, int repeat) 
    { 
     StringBuilder sb = new StringBuilder(); 

     List<char> domain = new List<char>(){list[start][0]}; 

     for (int i = start; i < list.Count; i++) 
     { 
      bool gap = false; 

      for (int j = 0; j < domain.Count; j++) 
      { 
       if (list[i][0] == domain[j]) 
       { 
        sb.Append(list[i]); 
        break; 
       } 
       else if (domain.Count < repeat) 
       { 
        domain.Add(list[i][0]); 
        sb.Append(list[i]); 
        break; 
       } 
       else 
       { 
        gap=true; 
        break; 
       } 
      } 

      if (gap) { break;} 
     } 

     return sb.ToString(); 
    } 


} 

Answer 3

Тот же вопрос мне, я написал этот код

public int getLargest(char [] s){ 
    if(s.length<1) return s.length; 
    char c1 = s[0],c2=' '; 
    int start = 1,l=1, max=1; 

    int i = 1; 
    while(s[start]==c1){ 
     l++; 
     start++; 
     if(start==s.length) return start; 
    } 

    c2 = s[start]; 
    l++; 

    for(i = l; i<s.length;i++){ 
     if(s[i]==c1 || s[i]==c2){ 
      if(s[i]!=s[i-1]) 
       start = i; 
      l++; 
     } 
     else { 
      l = i-start+1; 
      c1 = s[start]; 
      c2 = s[i]; 
      start = i; 
     } 
     max = Math.max(l, max); 
    } 
    return max; 
} 

Answer 4

Общее решение: самая длинная подстрока, которая содержит K уникальных символов.

int longestKCharSubstring(string s, int k) { 
    int i, max_len = 0, start = 0; 
    // either unique char & its last pos 
    unordered_map<char, int> ht; 

    for (i = 0; i < s.size(); i++) { 
     if (ht.size() < k || ht.find(s[i]) != ht.end()) { 
      ht[s[i]] = i; 
     } else { 
      // (k + 1)-th char 
      max_len = max(max_len, i - start); 
      // start points to the next of the earliest char 
      char earliest_char; 
      int earliest_char_pos = INT_MAX; 
      for (auto key : ht) 
       if (key.second < earliest_char_pos) 
        earliest_char = key.first; 
      start = ht[earliest_char] + 1; 
      // replace earliest_char 
      ht.erase(earliest_char); 
      ht[s[i]] = i; 
     } 
    } 
    // special case: e.g., "aaaa" or "aaabb" when k = 2 
    if (k == ht.size()) 
     max_len = max(max_len, i - start); 

    return max_len; 
} 

Answer 5

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.HashMap; import java.util.Iterator; import java.util.List; 
import java.util.Map; 

public class PrintLLargestSubString { 

    public static void main(String[] args){   String string = 
      "abcdefghijklmnopqrstuvbcdefghijklmnopbcsdcelfabcdefghi"; 
    List<Integer> list = new ArrayList<Integer>();   List<Integer> 
    keyList = new ArrayList<Integer>();  List<Integer> Indexlist = new 
    ArrayList<Integer>();  List<Integer> DifferenceList = new 
    ArrayList<Integer>();  Map<Integer, Integer> map = new 
    HashMap<Integer, Integer>();  int index = 0;  int len = 1;  int 
    j=1;  Indexlist.add(0);  for(int i = 0; i< string.length() ;i++) { 
     if(j< string.length()){ 
      if(string.charAt(i) < string.charAt(j)){ 
       len++; 
       list.add(len); 
      } else{ 
       index= i+1; 
       Indexlist.add(index); //     System.out.println("\nindex" + index);    
       len=1;    
      }   }   j++;  } //  System.out.println("\nlist" +list);   System.out.println("index List" +Indexlist); //  int n = 
    Collections.max(list); //  int ind = Collections.max(Indexlist); 
    //  System.out.println("Max number in IndexList " +n); 
    //  System.out.println("Index Max is " +ind); 

    //Finding max difference in a list of elements  for(int diff = 0; 
    diff< Indexlist.size()-1;diff++){   int difference = 
      Indexlist.get(diff+1)-Indexlist.get(diff); 
    map.put(Indexlist.get(diff), difference); 
    DifferenceList.add(difference);   } 
    System.out.println("Difference between indexes" +DifferenceList); //  Iterator<Integer> keySetIterator = map.keySet().iterator(); //  while(keySetIterator.hasNext()){ 
    //   Integer key = keySetIterator.next(); 
    //   System.out.println("index: " + key + "\tDifference " 
    +map.get(key)); // //  } //  System.out.println("Diffferenece List" +DifferenceList);  int maxdiff = Collections.max(DifferenceList);  System.out.println("Max diff is " + maxdiff);  //////  Integer 
    value = maxdiff;  int key = 0;  keyList.addAll(map.keySet()); 
    Collections.sort(keyList);  System.out.println("List of al keys" 
      +keyList); //  System.out.println(map.entrySet());   for(Map.Entry entry: map.entrySet()){   if(value.equals(entry.getValue())){ 
    key = (int) entry.getKey();   }  }  System.out.println("Key value of max difference starting element is " + key); 

    //Iterating key list and finding next key value   int next = 0 ; 
    int KeyIndex = 0;  int b;  for(b= 0; b<keyList.size(); b++) { 
     if(keyList.get(b)==key){ 
      KeyIndex = b;   }      }  System.out.println("index of key\t" +KeyIndex);   int nextIndex = KeyIndex+1;   System.out.println("next Index = " +nextIndex);   next = keyList.get(nextIndex); 
      System.out.println("next Index value is = " +next); 

      for(int z = KeyIndex; z < next ; z++) { 
       System.out.print(string.charAt(z));   } } 

      } 

Answer 6

Проблема может быть решена в O (N). Идея заключается в том, чтобы поддерживать окно и добавлять элементы в окно, пока оно не будет содержать меньше или равно 2, обновите наш результат, если это потребуется при этом. Если уникальные элементы превышают требуемые в окне, начните удалять элементы с левой стороны.

#code 
from collections import defaultdict 

def solution(s, k): 
    length = len(set(list(s))) 
    count_dict = defaultdict(int) 
    if length < k: 
    return "-1" 

    res = [] 
    final = [] 
    maxi = -1 

    for i in range(0, len(s)): 

    res.append(s[i]) 
    if len(set(res)) <= k: 
     if len(res) >= maxi and len(set(res)) <= k : 
     maxi = len(res) 
     final = res[:] 
     count_dict[maxi] += 1 

    else: 
     while len(set(res)) != k: 
     res = res[1:] 
     if maxi <= len(res) and len(set(res)) <= k: 
     maxi = len(res) 
     final = res[:] 
     count_dict[maxi] += 1 
    return len(final) 

print(solution(s, k))