longest sequence of same chars in a string

[sheesh342]

Hi,
I came across a problem to find out the longest sequence of same characters in a string. for example "food" would return "oo" and "rttrrrttttoooooo" would return "ooooo". Its feels disgusting when after developing large applications I am struggling on a basic programming question I guess I havent come across these type of problems in recent past.
Can someone help? Also it would be great if someone can point me where I can find more questions like this to practice.

 

[Diancecht]

Is the same or any character?

Cheers,
Dian

 

[sheesh342]

Sequence of same characters, not a mixed character sequence.

 

[Diancecht]

But the longest sequence of a known character or the longest sequence of any character?

Cheers,
Dian

 

[MoreFeo]

Something like:

public String returnLongest(String str)
{
  char car[] = str.toCharArray();
  char a = ' ';  //This will be the char with longest sequence
  char tmp;      //tmp char to iterate the array
  int c = 0;     //final counter
  int p = 1;     //tmp counter
  tmp = car[0];
  for (int i=1;i<str.length;i++)
  {
    if (car[i] == tmp)
    {
      p++;
    }
    else
    {
      if (p > c)
      {
        a = tmp;
        c = p;
      }
      tmp = car[i];
      p = 1;
  }

  char cres[] = new char[c];
  for (int j=0;j<c;j++)
  {
    cres[j] = a;
  }
  return new String(cres);
}

 

[MoreFeo]

Another option is to store first index and last index of the longest sequence and use subString(beginIndex,endIndex).

Maybe it's a better way.

 

[stefanwagner]

Here is a recursive solution:

String longestSequence (String s) 
{           
	if (s.length == 0) return "";
	char c = s.charAt (0);
	String subs = s.replaceAll ("(" + c + "+).*", "$1");
	int susi = subs.length ();
	String rest = longestSequence (s.substring (susi));
	if (susi >= rest.length) 
		return s.substring (0, susi)
	return	rest;
}

The longest sequence is either the sequence beginning at pos (0), or the longest sequence of that beginning thereafter.

don't visit my homepage:

http://home.arcor.de/hirnstrom/minis/index.html

 

[Diancecht]

Those are sollutions for any character. If you need to look for sequences of a known character, would be enough to store the length of the longest sequence.

Cheers,
Dian

 

[Trevoke]

Or you could use regular expressions?
I am just beginning in Java, so I don't know if this would work (but it works with Ruby's regexp parser):

http://rubular.com/r/q83F1yvDWv

Mind you, this is specific for 'o', and you'd check which match is the longest.

Tao Te Ching Discussions : Chapter 9 (includes links to previous chapters)
What is the nature of conflict?

 

[tsuji]

[1] A realization of the functionality using regex can look like this. It returns the longest run of certain character (ch, being well-escaped : attention) with n initially called with value 1. The return 0 means no match at all.
[tt]
int longestRun (String s, char ch, int n) {
int nm=n-1;
if (Pattern.compile("("+ch+"){"+n+",}").matcher(s).find()) {
nm=longestRun(s,ch,n+1);
}
return nm;
}
[/tt]
[1.1] The ch can in fact of any well-escaped particle to match in case one looks for more than a character.

[2] It can be called like this.
[tt]
String s_in="sample string: looooooooooongest ssssssssample";
char c_test='s';
int maxrun=[green]class_instance[/green].longestRun(s_in,c_test,1);
[/tt]