So finden Sie die längste Teilzeichenfolge, die zwei eindeutige sich wiederholende Zeichen enthält

Question

Die Aufgabe besteht darin, die längste Teilzeichenfolge in einer gegebenen Zeichenfolge zu finden, die aus zwei beliebigen sich wiederholenden Zeichen besteht.
Beispiel. in einer Eingabezeichenfolge „aabadefghaabbaagad“ ist die längste Zeichenfolge „aabbaa“

ich mit folgenden Lösung kam aber wollte sehen, ob es eine effizientere Art und Weise ist die gleiche

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

zu tun

Hier ist ein Hinweis, der Sie zu einem linearen Zeitalgorithmus führen könnte (ich nehme an, dass dies Hausaufgaben sind, daher werde ich nicht die gesamte Lösung geben): An dem Punkt, wo Sie ein Zeichen gefunden haben, das weder x noch entspricht y ist es nicht notwendig, den ganzen Weg zurück zu start + 1 zu gehen und die Suche neu zu starten. Nehmen wir die Zeichenfolge aabaaddaa. An der Stelle, an der Sie aabaa gesehen haben und das nächste Zeichen d ist, hat es keinen Sinn, die Suche bei Index 1 oder 2 neu zu starten, da Sie in diesen Fällen nur abaa oder baa erhalten, bevor Sie erneut d treffen. Sie können start direkt in Index 3 (der erste Index der letzten Gruppe von a s) verschieben, und da Sie bereits wissen, dass es eine zusammenhängende Sequenz von a s bis d gibt, können Sie i verschieben Index 5 und weiter.

Edit: Pseudocode unten.

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

so wie ich daran denke ist es in 2 Schritten zu lösen

• die gesamte Zeichenfolge scannen, um kontinuierliche Ströme von dem gleichen Buchstaben
• Schleife die extrahierten Segmente zu finden und kondensieren sie bis Du bekommst eine Lücke.

Auf diese Weise können Sie auch die Logik ändern für längste Unterkette beliebiger Länge scannen nicht nur 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

Gleiche Frage an mich, ich diesen Code schrieb

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

Eine allgemeine Lösung: Längste Teilzeichenfolge, die K eindeutige Zeichen enthält.

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

Das Problem kann in O (n) gelöst werden. Idee ist, ein Fenster beizubehalten und Elemente zu dem Fenster hinzuzufügen, bis es weniger oder gleich 2 enthält, aktualisieren Sie unser Ergebnis, wenn Sie dabei erforderlich sind. Wenn eindeutige Elemente die im Fenster erforderlichen Werte überschreiten, entfernen Sie die Elemente von der linken Seite.

#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))