nicht angemeldet
Effizientes Finden eines längsten Substrings
2 
Der Martin
0 
Gunnar Bittersmann
0 0 0 0 0 0 0 0 0 Der Martin
2
0
Effizientes Finden eines längsten Substrings
Hallo zusammen,
Hat jemand eine Idee, wie ich in einer Zeichenkette, die aus zwei unterschiedlichen Buchstaben besteht, effizient das längste Vorkommen einer identischen Buchstabenfolge finden kann?
Konkret sieht der String so aus:
ghghggghgghghghhhhhhhhhhhgghghghghghgh
Und ich will die längste Folge von h's finden.
Mein Ansatz war, eine Schleife zu bauen, die von i=1 bis zur Länge des Strings schaut, ob eine Zeichenkette mit i h's im String enthalten ist.
Scheint mir aber sehr ineffizient.
Kennt jemand eine bessere Lösung?
Gruß,
Frank
-
Hi,
Hat jemand eine Idee, wie ich in einer Zeichenkette, die aus zwei unterschiedlichen Buchstaben besteht, effizient das längste Vorkommen einer identischen Buchstabenfolge finden kann?
ja.
ghghggghgghghghhhhhhhhhhhgghghghghghgh
Und ich will die längste Folge von h's finden.
Mein Ansatz war, eine Schleife zu bauen, die von i=1 bis zur Länge des Strings schaut, ob eine Zeichenkette mit i h's im String enthalten ist.
Scheint mir aber sehr ineffizient.Scheint mir auch so.
Kennt jemand eine bessere Lösung?
Iteriere zeichenweise durch den String. Lass einen Zähler mitlaufen.
Triffst du auf ein 'h', erhöhe den Zähler.
Bei jedem anderen Zeichen setzt du den Zähler wieder auf 0, merkst dir aber vorher den Wert (ggf. auch noch die Position im String), wenn er größer als der bisher gefundene Wert war.Ciao,
Martin--
Keine Sorge, wir finden für jede Lösung ein Problem.
Selfcode: fo:) ch:{ rl:| br:< n4:( ie:| mo:| va:) de:] zu:) fl:{ ss:) ls:µ js:( -
@@Frank S.:
nuqneH
Und ich will die längste Folge von h's finden.
Kennt jemand eine bessere Lösung?s = der jeweilige String
l = 0
WHILE s nicht leer
ph = Position des ersten 'h' in s
IF ph > -1
s = Teilstring von s ab ph + 1
pg = Position des ersten 'g' in s
IF pg > -1
s = Teilstring von s ab pg + 1
l = max(l, pg - ph)
ELSE EXIT
ELSE EXITQapla'
--
Gut sein ist edel. Andere lehren, gut zu sein, ist noch edler. Und einfacher.
(Mark Twain)-
Hi,
s = der jeweilige String
l = 0
WHILE s nicht leer
ph = Position des ersten 'h' in s
IF ph > -1
s = Teilstring von s ab ph + 1
pg = Position des ersten 'g' in s
IF pg > -1
s = Teilstring von s ab pg + 1
l = max(l, pg - ph)
ELSE EXIT
ELSE EXITWenn ich das richtig sehe, ist die Zuweisung
l = max(l, pg - ph)
falsch. pg ist die Position des ersten g im ("neuindizierten") String s.
Beispiel:
s = "gggggghg"ph = 7
s = "g"
pg = 0
s = ""
l = max(0, 0 - 7) = 0Was falsch ist, da die längste "h"-Kette ein Zeichen lang ist.
Martins Lösung dürfte besser sein im Sinne der Effizienz.
Du hast weniger Stringoperationen, da du nur einmal durch den String durchiterieren musst, gleichzeitig brauchst du nur eine Variable für die Länge der aktuellen Zeichenkette, eine für die Länge der bisher Längsten.
Laufzeit O(n) in beiden Fällen, wobei die O-Notation bei dir einen Faktor 4 versteckt (um es mal unfachgemäß auszudrücken), wenn man naiv Stringfunktionen (indexOf, substr) verwendet, die allesamt O(n) ausmachen.Bis die Tage,
Matti
-
-
Hallo zusammen,
Hat jemand eine Idee, wie ich in einer Zeichenkette, die aus zwei unterschiedlichen Buchstaben besteht, effizient das längste Vorkommen einer identischen Buchstabenfolge finden kann?
Konkret sieht der String so aus:
ghghggghgghghghhhhhhhhhhhgghghghghghgh
Und ich will die längste Folge von h's finden.
Mein Ansatz war, eine Schleife zu bauen, die von i=1 bis zur Länge des Strings schaut, ob eine Zeichenkette mit i h's im String enthalten ist.
Scheint mir aber sehr ineffizient.Kennt jemand eine bessere Lösung?
Gruß,
FrankHi Frank,
ohne deine Umgebung zu kennen würde sagen splitten + sortieren. Wenn du das selber implementieren kannst, dann einmal durch die Zeichenkette iterieren und die Wechsel merken. Anschließend die Anzahl/Längen sortieren.
LG
-
Hallo,
ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.Gruß, Don P
-
Hallo,
ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.hängt davon, was man unter Eleganz versteht. Aber Sortieren soll schneller sein, als das zeichenweise durchlaufen (was der RegEx im Prinzip auch macht). Nein, ganz sicher nicht.
Martins Lösung *ist* effizient. Auf die Aufgabe konzentriert, leicht verständlich und dazu sparsam mit Ressourcen.
Freundliche Grüße
Vinzenz
-
Hallo,
abgesehen davon, dass ich die Vorgehensweise nicht als effizient ansehe ...
ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.... ist splitten natürlich überflüssig, wenn Finden aller Treffer ausreicht:
# Wir durchsuchen den Heuhaufen $haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh'; # nach dem Auftreten einer Folge von beliebig vielen, # mindestens jedoch einem "h" (der Nadel). # Die Gierigkeit von RegExp kommt uns dabei entgegen :-) # Nicht beachtet: [link:http://de2.php.net/manual/de/reference.pcre.pattern.modifiers.php@title=UTF-8-Problematik]. $pattern = '/h+/'; # Wir bereiten ein Array für das Ergebnis unserer Suche vor. $matches = array(); # und lassen alle Folgen von h finden, # alle Treffer sind wegen PREG_PATTERN_ORDER in $matches[0] (einem Array) if ([link:http://www.php.net/manual/de/function.preg-match-all.php@title=preg_match_all]($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) { # Wenn kein Fehler auftrat und es Treffer gab [link:http://de2.php.net/manual/de/function.rsort.php@title=rsort]($matches[0], SORT_STRING); # sortiere von längster nach kürzester echo $matches[0][0]; # und gebe die längste aus }Problemlos in ein Funktionchen umzubauen, die Heuhaufen und Nadel (der zu suchende Buchstabe) entgegennimmt und die längste Kette zurückgibt.
Ein Ansatz:/* Durchsucht die Zeichenkette $haystack nach dem Muster $pattern und gibt die längste Übereinstimmung zurück. Wird das Muster nicht gefunden, so wird eine leere Zeichenkette zurückgegeben. */ function biggest_substring($pattern, $haystack) { $result = ''; # fürs Ergebnis $matches = array(); # Zwischenlager if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) { rsort($matches[0], SORT_STRING); $result = $matches[0][0]; } return $result; }Aber: Sortieren ist lahm und - wie Martin gezeigt hat - überflüssig.
Freundliche Grüße
Vinzenz
-
Hallo Gunnar™,
abgesehen davon, dass ich die Vorgehensweise nicht als effizient ansehe ...
ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.auf das Sortieren sollte man auf jeden Fall verzichten, wenn man nur am größten Wert interessiert ist.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.
Wir ersetzen daher das Sortieren in meinem ersten Ansatz
> function biggest_substring($pattern, $haystack) { > $result = ''; # fürs Ergebnis > $matches = array(); # Zwischenlager > if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) { > rsort($matches[0], SORT_STRING); > $result = $matches[0][0]; > } > return $result; > }durch Reduzieren des Arrays auf einen einzigen Wert mittels array_reduce().
Benötigt wird eine Hilfsfunktion, die die längere von zwei Zeichenketten zurückliefert (die Zeichenkette selbst besteht ja aus lauter gleichen Buchstaben):
function rcmp($v, $w) { return strlen($v) > strlen($w) ? $v : $w; }und schreiben biggest_substring() entsprechend um:
function biggest_substring($pattern, $haystack) { $result = ''; # fürs Ergebnis $matches = array(); # Zwischenlager if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) { $result = array_reduce($matches[0], rcmp, ''); } return $result; }Damit wird das aufwendige Sortieren auf eine einfache Iteration durch das Ergebnisarray reduziert.
Freundliche Grüße
Vinzenz
-
[latex]Mae govannen![/latex]
Wir durchsuchen den Heuhaufen
$haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh';
[...]
$pattern = '/h+/';
[...]
Ok, das sucht nun aber ganz spezifisch nach "h". Sobald man die längste zusammenhängende Folge eines beliebigen gleichen Zeichens aus einer beliebigen Zeichenkette benötigt, ist der ganze Ansatz hinfällig. Also dann doch gleich die Iteration mit "merken". Stur lächeln und winken, Männer! Kai -- Dank Hixies Idiotenbande geschieht grade eben wieder ein Umdenken in Richtung "Mess up the Web".([suit](https://forum.selfhtml.org/?t=197497&m=1324775)) [SelfHTML-Forum-Stylesheet](http://selfhtml.knrs.de/#h_stylesheet)-
Hallo Kai,
Wir durchsuchen den Heuhaufen
$haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh';
[...]
$pattern = '/h+/';> > Ok, das sucht nun aber ganz spezifisch nach "h". die Erweiterung auf beliebige Zeichen ist trivial und in der Funktion eh' schon eingebaut, da man das Muster übergeben kann. `$pattern = '/' . $needle . '+/'; # Beispiel`{:.language-php} > Also dann doch gleich die Iteration mit "merken". Sag' ich was anderes? Freundliche Grüße Vinzenz-
[latex]Mae govannen![/latex]
die Erweiterung auf beliebige Zeichen ist trivial und in der Funktion eh' schon eingebaut, da man das Muster übergeben kann.
Und wenn man das spezifische Zeichen vorher nicht kennt?
'aaaabbbbgggjebjjebnjkhhhhhhjejjekehjjzzzzzzzzzzzjjjjj' <- hier sollte zzzzzzzzzzz gefunden werden
'kkkkkkkkkkkkkkkkkhhhejbwekenhuuuuuuuuhbehjebej' <- und hier kkkkkkkkkkkkkkkkkGibt es eine RegEx, die das leistet?
Also dann doch gleich die Iteration mit "merken".
Sag' ich was anderes?
Nein. Dennoch wollte ich anmerken, daß dein Ansatz nur dann anwendbar ist, wenn man das zu suchende Zeichen bereit vorher kennt.
Stur lächeln und winken, Männer!
Kai--
Dank Hixies Idiotenbande geschieht grade eben wieder ein Umdenken
in Richtung "Mess up the Web".(suit)
SelfHTML-Forum-Stylesheet-
Dennoch wollte ich anmerken, daß dein Ansatz nur dann anwendbar ist, wenn man das zu suchende Zeichen bereit vorher kennt.
Eine Kaffeemaschine kann das auch nicht, die macht nicht mal Michshakes.
-
Hallo,
Nein. Dennoch wollte ich anmerken, daß dein Ansatz nur dann anwendbar ist, wenn man das zu suchende Zeichen bereit vorher kennt.
der Fall interessierte mich nicht :-)
Klar, wenn man nur den ersten Satz des Ausgangsbeitrags zugrunde legt, kann es auch sein, dass einfach die längste gleichbuchstabige Zeichenkette zu suchen wäre:Hat jemand eine Idee, wie ich in einer Zeichenkette, die aus zwei unterschiedlichen Buchstaben besteht, effizient das längste Vorkommen einer identischen Buchstabenfolge finden kann?
Ich ging jedoch von der genauer spezifizierten Anforderung aus:
Konkret sieht der String so aus:
ghghggghgghghghhhhhhhhhhhgghghghghghgh
Und ich will die längste Folge von h's finden.Sprich: ich brachte eine Beispiellösung für die Aufgabe
"Suche die längste aufeinanderfolgende Kette des gleichen *bekannten*
Zeichens in einer Zeichenkette (die aus maximal zwei verschiedenen
Zeichen besteht."Alles darüber hinausgehende ist für mich ein Fall von YAGNI.
Leider hat sich Frank S. in diesem Thread bisher nicht mehr zu unserer Diskussion über *sein* Problem gemeldet :-(
Freundliche Grüße
Vinzenz
-
-
Hallo,
die Erweiterung auf beliebige Zeichen ist trivial und in der Funktion eh' schon eingebaut, da man das Muster übergeben kann.
und die Erweiterung auf beliebige Zeichen ist bei meinem Ansatz auch schnell gemacht. Die Änderung beschränkt sich darauf, nicht Zeichen[i]=='h' abzuprüfen, sondern Zeichen[i]==Zeichen[i-1]. Dann findet der Algorithmus die längste ununterbrochene Folge eines beliebigen Zeichens - sogar ohne das Zeichen vorher zu kennen.
Ciao,
Martin--
Die meisten Menschen werden früher oder später durch Computer ersetzt.
Für manche würde aber auch schon ein einfacher Taschenrechner genügen.
Selfcode: fo:) ch:{ rl:| br:< n4:( ie:| mo:| va:) de:] zu:) fl:{ ss:) ls:µ js:(-
Hi,
und die Erweiterung auf beliebige Zeichen ist bei meinem Ansatz auch schnell gemacht. Die Änderung beschränkt sich darauf, nicht Zeichen[i]=='h' abzuprüfen, sondern Zeichen[i]==Zeichen[i-1]. Dann findet der Algorithmus die längste ununterbrochene Folge eines beliebigen Zeichens - sogar ohne das Zeichen vorher zu kennen.
Ich kenne die Interna von PHP nicht, daher korrigiert mich bitte, wenn ich falsch liege.
Birgt der []-Operator nicht die Gefahr, sich ganz schnell O(n) Zugriffe einzuhandeln?Mit einem Char-Array fester Größe (wenn ich das aus C-Sicht sehe) könnte ich in O(1) auf ein beliebiges Zeichen zugreifen, bei Arrays (Strings) mit beliebiger Länge müsste ich mich da durchwursteln und wäre z.B. bei einer verketteten Liste bei O(n)?
Da wäre es vielleicht sogar sinnvoller, mit Iteratoren durch den Array durchzugehen. Wenn der Array nur eine einfach verkettete Liste ist, dann müsste man eine Referenz auf das letzte Zeichen (oder das Zeichen selber) speichern.
Bis die Tage,
Matti
-
-
Moin!
Wir durchsuchen den Heuhaufen
$haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh';
[...]
$pattern = '/h+/';> > > > Ok, das sucht nun aber ganz spezifisch nach "h". > > die Erweiterung auf beliebige Zeichen ist trivial und in der Funktion eh' schon eingebaut, da man das Muster übergeben kann. > > `$pattern = '/' . $needle . '+/'; # Beispiel`{:.language-php} Bei `echo "<p>".$_POST['usercomment']."</p>";`{:.language-php} jammern sofort alle. Warum nicht hier? Beachte IMMER den Kontextwechsel. $needle gehört selbstverständlich entsprechend behandelt. Zum Glück gibts da schon was: [linnk:http://www.php.net/preg\_quote] - Sven Rautenberg-
Hallo Sven,
ich sollte Schnellschüsse vermeiden, wenn die Zeit knapp ist.
die Erweiterung auf beliebige Zeichen ist trivial und in der Funktion eh' schon eingebaut, da man das Muster übergeben kann.
Beachte IMMER den Kontextwechsel. $needle gehört selbstverständlich entsprechend behandelt. Zum Glück gibts da schon was: [linnk:http://www.php.net/preg_quote]
völlig richtig, daher beispielsweise so:
$pattern = '/' . [link:http://de3.php.net/manual/de/function.preg-quote.php@title=preg_quote]($needle, '/') . '+/'; # BeispielFreundliche Grüße
Vinzenz
-
-
-
-
Hallo,
abgesehen davon, dass ich die Vorgehensweise nicht als effizient ansehe ...
ohne deine Umgebung zu kennen würde sagen splitten + sortieren.
Würde ich auch sagen, mit geeigneter RegEx splitten und nach Länge sortieren.
Dürfte trotz RegEx schneller und v.a eleganter sein als Zeichenweise durchlaufen.... ist splitten natürlich überflüssig, wenn Finden aller Treffer ausreicht:
Wir durchsuchen den Heuhaufen
$haystack = 'ghghggghgghghghhhhhhhhhhhgghghghghghgh';
nach dem Auftreten einer Folge von beliebig vielen,
mindestens jedoch einem "h" (der Nadel).
Die Gierigkeit von RegExp kommt uns dabei entgegen :-)
Nicht beachtet: [link:http://de2.php.net/manual/de/reference.pcre.pattern.modifiers.php@title=UTF-8-Problematik].
$pattern = '/h+/';
Wir bereiten ein Array für das Ergebnis unserer Suche vor.
$matches = array();
und lassen alle Folgen von h finden,
alle Treffer sind wegen PREG_PATTERN_ORDER in $matches[0] (einem Array)
if ([link:http://www.php.net/manual/de/function.preg-match-all.php@title=preg_match_all]($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) {
# Wenn kein Fehler auftrat und es Treffer gab
[link:http://de2.php.net/manual/de/function.rsort.php@title=rsort]($matches[0], SORT_STRING); # sortiere von längster nach kürzester
echo $matches[0][0]; # und gebe die längste aus
}> > Problemlos in ein Funktionchen umzubauen, die Heuhaufen und Nadel (der zu suchende Buchstabe) entgegennimmt und die längste Kette zurückgibt. > Ein Ansatz: > ~~~php > /* > Durchsucht die Zeichenkette $haystack nach dem Muster $pattern und gibt > die längste Übereinstimmung zurück. Wird das Muster nicht gefunden, so > wird eine leere Zeichenkette zurückgegeben. > */ > function biggest_substring($pattern, $haystack) { > $result = ''; # fürs Ergebnis > $matches = array(); # Zwischenlager > if (preg_match_all($pattern, $haystack, $matches, PREG_PATTERN_ORDER)) { > rsort($matches[0], SORT_STRING); > $result = $matches[0][0]; > } > return $result; > }Aber: Sortieren ist lahm und - wie Martin gezeigt hat - überflüssig.
Freundliche Grüße
Vinzenz
Huhu,
leider kenne ich mich mit php nicht so gut aus aber das sieht sehr formschön aus, was du da gepostest hast. Ich bin aber der Meinung, dass bei der Programmierung zur Lösung einer Problemstellung zuerst ein Konzept erstellt werden sollte. Performance ist sicherlich ein Punkt, den man berücksichtigen sollte aber letztendlich braucht man das Rad nicht immer wieder neu zu erfinden und wenn schon gewisse Funktionatitäten zur Verfügung stehen, dann sollte man diese auch nutzen. Ein Grundkonzept zur Lösung der Problemstellung war und ist ja immernoch splitten + sortieren.
Warum?
1. Splitten => aufteilen in Bestandteile
2. Sortieren => anordnen nach RegelnDas ist erstmal nur ein Grundmuster und wiedersprich letztendlich auch keiner Implementierung, wie auch immer diese aussehen mag.
Weiterhin muss man für die Implementierung verschiedenen Faktoren berücksichtigen, die auch das Funktionsverhalten beinflussen.
1. Ist die Eingabe variabel? (wurde ja schon geklärt)
2. Was soll geschehen, wenn es keine längste Wiederholung gibt?Meines Erachtens ist die Sortierung das kleinere Übel, denn ein Längenvergleich findet auf jedenfall statt. Von mir aus kann eine Sortierung auch durch eine Max-Funktion ersetzt werden aber man bedenke Punkt 2 => ist eine Max-Funktion eindeutig?
Jetzt wo ich so drüber nachdenke ^^ würde ich folgende Schritte durchführen (wie auch immer).
1. Splitten (Aufteilen)
2. Gruppieren nach Länge
3. Sortieren nach Länge (Gruppierung)
4. Auswahl über Schlüssel (wer ist in der Gruppe mit den meisten Wiederholungen)
5. Prüfen ob eindeutigLG
-
@@reborn:
nuqneH
das sieht sehr formschön aus, was du da gepostest hast.
Das kann man von dem, was du da gepostest hast, nicht sagen. Zitiere bitte sinnvoll, nicht alles!
Jetzt wo ich so drüber nachdenke ^^ würde ich folgende Schritte durchführen (wie auch immer).
Wenn die Aufgabe ist, „in einer Zeichenkette, die aus zwei unterschiedlichen Buchstaben besteht, effizient […] die längste Folge von h's [zu] finden“ (beachte „effizient“!), dann muss man keinen deutlich aufwendigeren Algorithmus implementieren, der in einer beliebigen Zeichenfolge die längste Folge eines beliebigen Zeichens findet.
Qapla'
--
Gut sein ist edel. Andere lehren, gut zu sein, ist noch edler. Und einfacher.
(Mark Twain)-
Huhu,
ja ich habe halt nur das Standardformular genutzt, welches mir das Forum bietet. Wenn ich da zuerst was löschen muss, dann ist das mein Verschulden. Danke für den Hinweis.
Dass die gestellte Aufgabe ansich erfüllt wurde ist richtig, dann erübrigt sich ja jegliche Diskussion.
LG
-
-
- Was soll geschehen, wenn es keine längste Wiederholung gibt?
Wie soll so ein Fall aussehen, in dem die längste Wiederholung nicht mal aus Null Zeichen also '' besteht? Oder willst Du sagen, eine Wiederholung ist es nur, wenn es zwei Zeichen sind und selbst bei keiner Wiederholung muß es mindestens ein Zeichen sein?
aber man bedenke Punkt 2 => ist eine Max-Funktion eindeutig?
Wenn man nicht die Position des Strings, sondern nur den String selber haben will und sich die in Frage kommenden Strings nur aus einem Zeichen zusammensetzen, sich außer in der Länge also nicht unterscheiden, dann ja.
- Gruppieren nach Länge
- Sortieren nach Länge (Gruppierung)
Wozu die Gruppierung?
-
Hi Texter,
die Fragestellung ist ja "Was ist eine effiziente Ermittlung des längsten Vorkommens einer identischen Buchstabenfolge". Es wurden verschiedene Ansätze vorgestellt und ich wollte nur darauf hinweisen – so glaube ich – dass diese nicht die Fragestellung erfüllen. Was ist mit der Zeichenkette "aabb"? Meines Erachtens nach sollte die "Funktion" nicht "aa" zurückliefern. Letztendlich muss die gesamte Eingabezeichenkette überprüft werden und es sind weitere Überprüfungen erforderlich um ein eindeutiges Ergebnis zu liefern. Ich habe ja nur Schritte aufgeführt, die es zu erfüllen gilt und von denen ich denke, dass sie erforderlich sind – egal wie die Umsetzung aussieht.
Die Gruppierung (nach Länge) habe ich an Platz 2 gestellt, weil ich vermute, dass sie schneller ist als eine sofortige Sortierung.
LG
-
die Fragestellung ist ja "Was ist eine effiziente Ermittlung des längsten Vorkommens einer identischen Buchstabenfolge". Es wurden verschiedene Ansätze vorgestellt und ich wollte nur darauf hinweisen – so glaube ich – dass diese nicht die Fragestellung erfüllen.
Die Fragestellung besteht aus mehr als dem einen Satz. Der Buchstabe aus dem die Zeichenkette bestehen soll wird vorgegeben.
Was ist mit der Zeichenkette "aabb"? Meines Erachtens nach sollte die "Funktion" nicht "aa" zurückliefern.
Wenn nach dem längsten Vorkommen von a gesucht wird, dann doch. Und bei der Zeichenkette "aabbaa" ebenfalls und bei "bbb" sollte "" zurückgegeben werden.
Die Gruppierung (nach Länge) habe ich an Platz 2 gestellt, weil ich vermute, dass sie schneller ist als eine sofortige Sortierung.
Aber eine Gruppierung ist sinnlos, ein Exemplar reicht aus. Wenn man weiß aus welchem Zeichen die Zeichenkette besteht, bedarf es noch nicht mal eines Exemplars, dann reicht die Länge aus.
-
-
-
-
-