# Längster Run



## yidaki (12. Juli 2004)

Hallo zusammen....
ich hab ein kleines Problem. Ich möchte aus einem String auslesen, welches Zeichen am häufigsten vorkommt. Das Programm das ich geschrieben hab läuft soweit ganz gut, bis auf das kleine Problem, dass wenn der längste run am ende der zeichenkette steht.

```
String run = "aabbbcddddeefffdddddddddddddddd ";
```
dann müsste er noch einmal in meine anweisung reinspringen doch mir fällt im moment nix gescheites ein.
hier die If-Anweisung

```
if (str.charAt(counts) != str.charAt(i))
```

gruß


----------



## Trespasser (12. Juli 2004)

Ich würde das mit einem Zweidimensionalen Array machen...
Jede Spalte für einen Buchstaben und darunter die Anzahl.

dann würde ich jeden index durchgehen und bei dem jeweiligen buchstaben um
eins erhöhen.

Vielleicht gibts noch eine bessere Methode, aber mir fällt auf die schnelle nur 
die ein.

mfg


----------



## squeaker (12. Juli 2004)

Ich würde mittels StringReader den String Zeichen für Zeichen durchgehen. In einer Temporären variable speicherst du das vorhergehende Zeichen um Zeichenwechsel zu erkennen. Wenn die Zeichen (aktuelles und vorhergehendes) gleich sind, erhöhst du den counter. Wenn sie verschieden sind, überprüfst du, ob der counter größer ist als der größte bisher gefundene, wenn ja, speicherst du den counter, das Zeichen sowie den Anfang der Kette zwischen. Dann counter zurücksetzen auf 1 und weitersuchen.
Am Ende hast du dann den größten Run an zeichen.


In pseudocode:


```
while (wir haben noch zeichen zu lesen) {
   prev=temp;
   temp=stringReader.read();
   temp_p++;
   if (temp==prev) {
      counter++
   } else {
     if (counter=max_counter) {
       max_counter=counter;
       max_char=prev;
       position=temp_p-counter;
     }
     counter=1; //siehe unten - 1 ist richtig, nicht 0
   }
}
```

so ungefähr. Ich kann's leider hier nicht programmieren - daher nur der vage Hinweis (ausserdem ist es sicher eine gute Übung - im Pseudocode sind sicher noch kleine Fehler).


----------



## yidaki (12. Juli 2004)

Naja, es sollte eigentlich schon mit nem normalen String passieren.... 
falls der code zu wenig sein sollte kann ich den rest schicken... das programm hat in dem fall oben als ausgabe

längster run : dddd
run.lenght :   4 
...

er müsste nur noch einmal am schluss in die aufgeführte if anweisung reinspringen dann währe alles im lot

gruß


----------



## Trespasser (12. Juli 2004)

Noch was squeaker derine Methode ist zwar  Ok, doch hat sie einen Haken:

```
: String s="abb";
```

a würde 0 bekommen.


----------



## squeaker (12. Juli 2004)

ich sagte doch - kleine Fehler sind noch drin - ausserdem wird vor dem lesen von a ein wechselnder Run entdeckt und damit der counter auf 1 gesetzt.

Zum Thema String und StringReader: ein StringReader kann man ganz einfach aus einem String basteln:

String s="abb";
StringReader sr=new StringReader(s);

Warum soll man sich auf nur einen Teil der Werkzeuge beschränken, wenn man den ganzen Schrank voll hat.


----------



## Trespasser (12. Juli 2004)

sorry habe mich verlesen.
aber im code schreibst du: cnt=0;

mfg


----------



## squeaker (12. Juli 2004)

Du hast natürlich recht - ich wollte 1 schreiben. Danke für den Hinweis.


----------



## Trespasser (12. Juli 2004)

Ich hätte noch eine Optimierung für deine Methode:

er braucht sich nicht die Position zu merken,außer aus statistischen Gründen ,wo welcher Run war. 
Er kennt ja das Zeichen und wie lang der Run ist somit könnte er die zeichen in einer for oder while schleife ausgeben.

Wenn eher statistische Gründe vorhanden sind, würde ich auf emine Methode zurückgreifen, da jeder Run gespeichert wird,  plus Anzahl.

mfg


----------



## Thomas Darimont (12. Juli 2004)

Hallo!

Siehe:


```
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LongestRun {

	public static void main(String[] args) {
		System.out.println(
			getLongestRun("aqqqqhkjdhkjhkjhdassdaewwzwzzzzwzqzzzzzzwwiiiiiiiqwiwqiweqwooooooooooooooooooas"));
	}

	/**
	 * @param string
	 */
	private static String getLongestRun(String string) {
		int len = string.length();
		int cnt = 0;
		char c = 0;
		char cOld = string.charAt(0);
		Map map = new HashMap();

		for (int i = 0; i < len; i++) {
			c = string.charAt(i);

			if (c != cOld) {
				String key = "" + cOld;
				Integer integer = (Integer) map.get(key);

				if (integer == null || integer.intValue() < cnt) {
					map.put(key, new Integer(cnt));
				}
				cnt = 0;
			}
			cnt++;
			cOld = c;
		}

		int max = cnt;
		String maxKey = cOld + "";

		for (Iterator iter = map.keySet().iterator(); iter.hasNext();) {
			Object key = iter.next();
			Integer i = (Integer) map.get(key);
			if (i.intValue() > max) {
				max = i.intValue();
				maxKey = (String) key;
			}
		}
		return maxKey + " kommt mit " + max + " mal am häufigsten direkt hintereinander in der übergebenen Zeichenkette vor";
	}
}
```

Gruß Tom


----------



## Trespasser (12. Juli 2004)

habe mir schon gedacht wo dein Kommentar-Lösung bleibt.
Hätte mich gewundert wenn von dir nichts gekommen wäre 

mfg


----------



## yidaki (12. Juli 2004)

So hab´s doch noch hinbekommen.... ;-)

thx



```
public class LaengsterRun {
	public static void main(String[] args) {
		String run = "abdddddddddefddddd";
		run(run);
	}
	public static void run(String str) {
		int counta = 0;
		int count = 0;
		String temp = "";
		String längsterRun = "";
		try {
			for (int i = 0; i <= str.length() - 1; i++) {
				if (str.charAt(counta) == str.charAt(i)) {
					temp += str.charAt(i);
					count += 1;
				}
				if ((str.charAt(counta) != str.charAt(i))
					|| count == str.length()) {
					counta = i;
					i = counta - 1;
					if (längsterRun.length() < temp.length()) {
						längsterRun = temp;
					}
					temp = "";
				}
			}
			System.out.println(
				"Der Längste Run des Strings: "
					+ str
					+ "\nist: "
					+ "\""
					+ längsterRun
					+ "\""
					+ "\nmit: "
					+ längsterRun.length()
					+ " Zeichen");
		} catch (IndexOutOfBoundsException s) {
			System.out.println("s");

		}
	}
}
```


----------



## Thomas Darimont (12. Juli 2004)

```
} catch (IndexOutOfBoundsException s) {
			System.out.println("s");

		}
```

sollte wohl:


```
} catch (IndexOutOfBoundsException s) {
			System.out.println(s);

		}
```

Heißen ... ;-)

Okay, wenn man mal das Gehirn einschaltet und das Ganze Collection Gerümpel wegläßt gehts auch :


```
public class LongestRun {

	public static void main(String[] args) {
		System.out.println(getLongestRun("aqqqqhkjdhkjhkjhdassdaewwzwzzzzwzqzzzzzzwwiiiiiiiqwiwqiweqwooooooooooooooooooas"));
	}

	/**
	 * @param string
	 */
	private static String getLongestRun(String string) {
		int len = string.length();
		int cnt = 0;
		char c = 0;
		char cOld = string.charAt(0);

		char maxC = 0;
		int maxCnt = 0;

		for (int i = 0; i < len; i++) {
			c = string.charAt(i);

			if (c != cOld) {
				if (maxCnt < cnt) {
					maxC = cOld;
					maxCnt = cnt;
				}
				cnt = 0;
			}
			cOld = c;
			cnt++;
		}
		
		return maxC
			+ " kommt mit "
			+ maxCnt
			+ " mal am häufigsten direkt hintereinander in der übergebenen Zeichenkette vor";
	}
}
```

Gruß Tom

Gruß Tom


----------



## Trespasser (12. Juli 2004)

was genau macht

Integer integer = (Integer) map.get(key);

				if (integer == null || integer.intValue() < cnt) {
					map.put(key, new Integer(cnt)); .....
                                }

für was ist der Integer.
Habe noch nie was mit HashMaps gemacht und aus der API wird nicht genaus ersichtlich was da eigentlich passiert.

mfg


----------



## Thomas Darimont (12. Juli 2004)

Hallo!

HashMap ist ein sogenannter Assoziativer Speicher. D.h. du kannst in ihm Schlüsselwertpaare speichern wobei Schlüssel und Wert Referenztypen sein müssen. Da ich mir in der Map die jeweiligen Auftrittshäufigkeiten der Buchstaben hintereinander gemerkt habe und diese Häufigkeiten jedoch primitive int's sind musste ich diese int's in ihre Objektrepresentation (Ihre Wrapper Typen) umwandeln und dann erst in der HashMap speichern.

HashMaps brauchen für den Zugriff auf ein bestimmtes Wert eine konstante Zeit. 
http://www.galileocomputing.de/open...0005256DieKlasseHashMapundassoziativeSpeicher

Gruß Tom


----------



## yidaki (12. Juli 2004)

hab den code ein bisschen verändert und da ist wohl was verloren gegangen ;-)

also dann


----------



## Trespasser (12. Juli 2004)

Was passiert wenn der String s="aaabbaaa" so aussieht. Da
kann die Map nicht mehr  welcher Key dann gemeint ist bzw. überschreibt  die
Map dann bei put den anderen Wert der bei aaa als Value gespeichert ist?


----------

