CareerCup

The longest consecutively repeating character repeats k times. Return all characters that repeat k times in the order that they appear left to right

static List<String> getLongestConsecutiveChar(string S)
    {
        var index=0;
        var max=0;
        var len=1;
        var result=new List<String>();
        while(index<S.Length)
        {
            while(index <S.Length-1 && S.Substring(index,1)==S.Substring(index+1,1) )
            {
                len++;
                index++;
            }
            if(len>max)
            {
                result.Clear();
                max=len;
            }
            if(len==max)
            {
                arr.Add(S.Substring(index,1));
            }
            
            len=1;
            index++;
        }
        
        return result;
    }

Can someone explain the question?

O(n) solution

public class LongestCharacterSequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		char[] characterSequence = new char[] { 'a', 'a', 'a', 'b', 'c', 'c',
				'c', 'c', 'c', 'd', 'd' };

		System.out.println("Longest char sequence :"
				+ getLongestConsecutiveChar(characterSequence));

	}

	private static char getLongestConsecutiveChar(char[] charSequence) {

		char maxConscutiveChar = charSequence[0];
		int maxCharacterCount = 0;
		int tempCharacterCount = 1;
		char tempChar = charSequence[0];

		for (int index = 1; index < charSequence.length; index++) {
			if (charSequence[index] != tempChar) {
				if (tempCharacterCount > maxCharacterCount) {
					maxCharacterCount = tempCharacterCount;
					maxConscutiveChar = tempChar;
				}

				tempChar = charSequence[index];
				tempCharacterCount = 1;

			} else {
				tempCharacterCount++;
			}

		}

		return maxConscutiveChar;
	}
}

public static ArrayList<Character> solve(String in) {
		ArrayList<Character> lst = new ArrayList<Character>();

		if(in == null) 
			return lst;

		String s = in.replace(" ", "");

		if(s.isEmpty())
			return lst;

		lst.add(s.charAt(0));
		int maxSeq = 1;
		int seq = 1;

		for(int i = 1; i < s.length(); i++) {

			if(s.charAt(i) == s.charAt(i-1))  {
				seq++;
			} else {
				seq = 1;
			}

			if(seq > maxSeq) {
				maxSeq = seq;
				lst.clear();
				lst.add(s.charAt(i));
			} else if(seq == maxSeq) {
				lst.add(s.charAt(i));
			}

		}

		return lst;
	}

C++ in O(n)

vector<char> getLCC(const string in) {
	vector<char> out;
	char last = '\0';
	int lastCount = 1;
	int maxSeq = 1;
	for(size_t i = 0; i < in.size(); ++i) {
		// check if it is a char (we dont want whitespaces)
		if( (in[i] >= 'a' && in[i] <= 'z') || (in[i] >= 'A' && in[i] <= 'Z') ) {
			if(in[i] == last) {
				// increase counter for current char
				++lastCount;
				if(lastCount > maxSeq) {
					// reset storage if max len is langer than previously thought
					maxSeq = lastCount;
					out = vector<char>();
				}
			}
			else {
				// reset last and lastCount
				lastCount = 1;
				last = in[i];
			}

			if(lastCount == maxSeq) {
				out.push_back(in[i]);
			}
		}
	}
	return out;
}

public class GetLongestConsecutiveChar {
	private static List<Character> getLongestConsecutiveChar(String s) {
        int max=0;
        int len=1;
        List<Character> res=new ArrayList<Character>();
        for(int i=0;i<s.length()-1;i++){
        	if(s.charAt(i)==' '){
        		len=1;
        		continue;
        	}
            while(i<s.length()-1 && s.charAt(i)==s.charAt(i+1) ){
                len++;
                i++;
            }
            if(len>max){
                res.clear();
                res.add(s.charAt(i));
                max=len;
            } else if(len==max){
                res.add(s.charAt(i));
            }
            len=1;
        }        
        return res;
	}
	public static void main(String[] args) {
		String s1="this is a test sentence";
		String s2="thiis iss a teest seentennce";
		String s3="thiiis iss aa teeest seentennnce";
		String s4="thiiiis iss a teeest seeentennncccce";
		System.out.println(getLongestConsecutiveChar(s1));
		System.out.println(getLongestConsecutiveChar(s2));
		System.out.println(getLongestConsecutiveChar(s3));
		System.out.println(getLongestConsecutiveChar(s4));
	}	
}

public char getLongestConsecutiveChar(String str) {
        char[] chars = str.toCharArray();
        char maxFrequentChar = chars[0];
        int maxFrequency = 1;
        char maxFrequentCharSoFar = chars[0];
        int maxFrequencySoFar = 1;

        for (int i = 1; i < chars.length; i++) {
            if (chars[i] != chars[i - 1]) {
                if (maxFrequencySoFar > maxFrequency) {
                    maxFrequency = maxFrequencySoFar;
                    maxFrequentChar = maxFrequentCharSoFar;
                }
                maxFrequencySoFar = 1;
                maxFrequentCharSoFar = chars[i];
            } else {
                maxFrequencySoFar++;
            }
        }
        if (maxFrequencySoFar > maxFrequency) {
            maxFrequentChar = maxFrequentCharSoFar;
        }
        return maxFrequentChar;
    }

def get_longest_consecutive_chars(string):
    if len(string) == 0:
        return [0, set()]

    max = 1
    max_char = set(string[0])
    index = 1
    current = 1
    while index < len(string):
        if string[index] == string[index - 1]:
            current += 1
        else:
            current = 1

        if current == max:
            max_char.add(string[index])
        if current > max:
            max = current
            max_char = set(string[index])

        index += 1

    return [max, max_char]

public class LongestConsecutiveChar {

public static char getLongestConsecutiveChar(String input){
int [] chars = new int[26];
int maxValue = 0;
int maxIndex = 0;
for(int i=0; i<input.length();i++){
chars[input.charAt(i) - 'a']++;
if(i+1 < input.length() && input.charAt(i+1) != input.charAt(i) && maxValue < chars[input.charAt(i) - 'a']){
maxValue = chars[input.charAt(i) - 'a'];
maxIndex = i;
chars[input.charAt(i) - 'a'] = 0;
}
if(i+1 == input.length() && maxValue < chars[input.charAt(i) - 'a'] ){
maxValue = chars[input.charAt(i) - 'a'];
maxIndex = i;
chars[input.charAt(i) - 'a'] = 0;
}
}
System.out.println("maxValue is " + maxValue + " char is " + input.charAt(maxIndex));

return input.charAt(maxIndex);
}

public static void main (String args[]){
getLongestConsecutiveChar("aabbbcdddaaaaaaaaaaaaaaaaddeffffffffffffadddddddddddddddddddddddddddddda");
}
}

public class LongestConsecutiveChar {
	
	public static char getLongestConsecutiveChar(String input){
		int [] chars = new int[26];
		int maxValue = 0;
		int maxIndex = 0;
		for(int i=0; i<input.length();i++){
			chars[input.charAt(i) - 'a']++;
			if(i+1 < input.length() && input.charAt(i+1) != input.charAt(i) && maxValue < chars[input.charAt(i) - 'a']){
				maxValue = chars[input.charAt(i) - 'a'];
				maxIndex = i;
				chars[input.charAt(i) - 'a'] = 0;
			}
			if(i+1 == input.length() && maxValue < chars[input.charAt(i) - 'a'] ){
				maxValue = chars[input.charAt(i) - 'a'];
				maxIndex = i;
				chars[input.charAt(i) - 'a'] = 0;
			}
		}
		System.out.println("maxValue is " + maxValue + " char is " + input.charAt(maxIndex));
		
		return input.charAt(maxIndex);
	}
	
	public static void main (String args[]){
		getLongestConsecutiveChar("aabbbcdddaaaaaaaaaaaaaaaaddeffffffffffffadddddddddddddddddddddddddddddda");
	}
}

public String getLongestConsecutiveChar (String s){
		int tail = 0 , maxLen = 0;
		String result = "";
		for (int i = 1 ; i < s.length() ; ++i) {
			if (s.charAt(i) != s.charAt( i -1)) {
				if (i - tail > maxLen) {
					maxLen = i - tail;
					result = s.substring(tail, i) ;
				}
				tail = i ;
			}
		}
		if (s.length() - tail > maxLen) {
			result = s.substring(tail, s.length()) ;
		}
		return result ;

}

public static Collection<Character> getLongestConsecutiveChar(String s) {
	s.length() < 1) return null;
	char lastChar = s.charAt(0);
	int count = 1;
	int maxCount = count;

	for (int i = 1; i < s.length(); i++) {
		count = (lastChar == s.charAt(i)) ? count + 1 : 1;
		maxCount = Math.max(maxCount, count);
		lastChar = s.charAt(i);
	}
	
	ArrayList<Character> result = new ArrayList<Character>();
	for (int i = 1; i < s.length(); i++) {
		count = (lastChar == s.charAt(i)) ? count + 1 : 1;
		if (count == maxCount) result.add(s.charAt(i));
		lastChar = s.charAt(i);
	}
	return result;
}

void Main()
{
	Console.WriteLine(LongestRepeatingChar("this is a test sentence"));// => [t, h, i, s, i, s, a, t, e, s, t, s, e, n, t, e, n, c, e]
	Console.WriteLine(LongestRepeatingChar("thiis iss a teest seentennce"));// => [i, s, e, e, n]
	Console.WriteLine(LongestRepeatingChar("thiiis iss aa teeest seentennnce"));//  => [i, e, n]
	Console.WriteLine(LongestRepeatingChar("thiiiis iss a teeest seeentennncccce"));// => [i, c]
}


	
	public static List<char> LongestRepeatingChar(string S)
	{
		var result = new Dictionary<char, List<int>>();
		char prev = ' ';
		if(S.Length > 0)
		{
			prev = S[0];
			result.Add(S[0], new List<int>(){1});	
		}
		
		int count = 1;
		int max = 0;
		for(int i = 1; i < S.Length; i++)
		{
			char s = S[i];
			if(s == prev)
			{
				count++;
			}
			else
			{
				if(result.ContainsKey(prev))
				{
					result[prev].Add(count);
				}
				else
				{
					result.Add(prev, new List<int>(){count});
				}
				
				if(max < count)
					max = count;
				count = 1;
				prev = s;
			}
		}
		
		if(result.ContainsKey(prev))
		{
			result[prev].Add(count);
		}
		else
		{
			result.Add(prev, new List<int>(){count});
		}
		
		if(max < count)
			max = count;
		
		Console.WriteLine(result);
		List<char> lResult = new List<char>();
		foreach(char s in S)
		{
			if(s != ' ')
			{
				var list = result[s];
				for(int i = 0; i < list.Count; i++)
				{
					int r = list[i];
					if(r == max)
					{
						lResult.Add(s);
						list.RemoveAt(i);
						break;
					}
				}
			}
		}
		
		return lResult;
	}

string = "aaaabbcccdddddddddddddd"

i = 1
max = string.length
before_char = string[0]
max_count = 0
count_hash = {}

while i <= max do 
  before_char = string[i-1]	
  current_char = string[i]  
  if before_char == current_char
    max_count+=1
  else
    count_hash[before_char] = max_count+1    
    max_count=0
  end
  i+=1
end

count_hash.max_by { |k,v| v }

function getPattern(str) {
    str = str.split('');
    var hash = {},
        currentChar = str[0],
        currentSequenceLength = 1,
        maximumSequenceLength = 0,
        result = [];

    for (i = 0; i < str.length; i++) {
        if (currentChar !== str[i + 1]) {
            if (/\w/.test(currentChar) === true) {
                hash[currentSequenceLength] = hash[currentSequenceLength] || [];
                hash[currentSequenceLength].push(currentChar);
                maximumSequenceLength = Math.max(maximumSequenceLength, currentSequenceLength);
            }

            currentChar = str[i + 1];
            currentSequenceLength = 1;
        } else {
            currentSequenceLength++;
        }
    }

    return hash[maximumSequenceLength];
}

Here is a solution in O(n) growth using a hash-table to store the count of characters and a list of the letters that repeat that amount of times while keeping the maximum value to search later.

public static List<char> getLongestConsecutiveChars(string S)
{
	if(string.IsNullOrEmpty(S)) return null;

	int count = -1;
	int max = -1;
	char prev = '\0'; // Initial value does not matter

	var ht = new Dicitionary<int, List<char>>();
	foreach(char s in S)
	{
		if(s != prev)
		{
			if(!ht.ContainsKey(count))
			{
				ht.Add(count, new List<char>());
			}

			ht[count].Add(prev);
			if(count > max)
			{
				max = count;
			}

			count = 0;
			prev = s;
		}
		else
		{
			count++;
		}
	}

	// Adding last one
	if(!ht.ContainsKey(count))
	{
		ht.Add(count, new List<char>());
	}

	ht[count].Add(prev);
	if(count > max)
	{
		max = count;
	}

	return ht[max];
}

public static List<Character> getLongestConsecutiveChar (String s) {
		List<Character> list = new LinkedList<Character>();
		int max = 0;
		int left = 0;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(left) != s.charAt(i)) {
				if (max == i-left) {
					list.add(s.charAt(left));
					left = i;
				} else if (max < i-left) {
					list.clear();
					list.add(s.charAt(left));
					max = i-left;
					left = i;
				} else {
					left = i;
				}
			}
		}
		System.out.println("here"+max);
		return list;
	}

Time complexity: O(n)
Space complexity: O(n) if you include the result set, O(1) otherwise
Basically, we keep a running total of how many times we've consistently hit the current character, as well as the maximum streak we've had thus far. Whenever we hit a new character, we check if our current streak is better than max, if so, clear the results and update the max streak; if it is the same, just add the current character to it (and if less, do nothing). Then restart the current streak. This doesn't require us to store a previous char because we look forward one character rather than backward, as the null terminator will be recognized as the end of our current streak. Note the isspace check, as the first result set in the example implies that we only want non-space characters in the result.

#include <vector>
#include <string>

using namespace std;

vector<char> getLongestConsecutiveChar(string str)
{
	int curStreak = 0, maxStreak = 0;
	vector<char> results;

	for (int i = 0; i < str.length(); ++i)
	{
		while (isspace(str[i])) // Skip over spaces
		{
			++i;
		}
		++curStreak;
		if (str[i] != str[i + 1])
		{
			if (curStreak > maxStreak)
			{
				maxStreak = curStreak;
				results.clear();
				results.push_back(str[i]);
			}
			else if (curStreak == maxStreak)
			{
				results.push_back(str[i]);
			}
			curStreak = 0;
		}
	}
	return results;
}

If we can afford O(N) space, then we can use it to store an array of 'count' of consecutive chars:

E.g., the following input string would result in the following count array (we don't count space)
'thiiis iss aa teeest seentennnce' => 11123101120120112311011211112311

It will take O(N) time to get this count array, then another O(N) to loop thru count array to print the character at position with max count value.

This algorithm use list to keep the longest consecutive chars.
Running time is O(N), where N is the length of the input string.

#include<list>
#include<string>
#include<iostream>
#include<climits>
using namespace std;

list<char> getlLongestConsecutiveChar(string input)
{
  list<char> found;
  char c = input[0];
  int count = 1;
  int max = INT_MIN;

  for (int i = 1; i < input.length(); i++)
  {
    if( input[i] == ' ')
      continue;
    if (c != input[i])
    {
      if (count > max)
      {
        if(found.size() >0)
          found.clear();
        found.push_back(c);
        max = count;
      } else if (count == max)
      {
        found.push_back(c);
      }
      count = 1;
      c = input[i];
    } else {
      count++;
    }
  }
  return found;
}

private List<String> getLongestConsecutiveChar(final String text) {
        if (text == null || text.length() == 0){
            return null;
        }

        List<String> result = new ArrayList<>();
        String textWithoutSpaces = text.replaceAll(" ","");
        int length = textWithoutSpaces.length();
        int max = 0;
        int counter = 0;
        char currentChar;
        Character previousChar = null;

        // Get max
        for (int i=0; i<length; i++){
            currentChar = textWithoutSpaces.charAt(i);
            if (previousChar == null || currentChar == previousChar){
                counter++;
            }
            else {
                if (counter > max){
                    max = counter;
                }
                counter = 1;
            }

            previousChar = currentChar;
        }

        // Fill the results
        previousChar = null;
        for (int i=0; i<length; i++){
            currentChar = textWithoutSpaces.charAt(i);
            if (max == 1){
                result.add(Character.toString(currentChar));
            }
            else if (previousChar == null || currentChar == previousChar){
                counter++;
                if (counter == max){
                    result.add(Character.toString(currentChar));
                }
            }
            else {
                counter = 1;
            }

            previousChar = currentChar;
        }

        return result;
    }

We loop throught and check each character with the one right before it in a while loop to see if a sequence is emerging. When the while loop is done (the streak ends), we see if we update the max value, and if we do, we also update the longest character.
Default returns the first character in the string.

char longestConsecChar(String s) {
	
	int k, cnt = 1;
	char longest = s[0];

	for (int i = 1; i < s; i++) {

		while (s[i] == s[i-1] && i < s) {

			cnt++;
			i++;
		}

		if (k < cnt) { 

			k = cnt;
			longest = s[i-1]; 
		}

		cnt = 0;
	}
}

char[] chars = "aaaabbcccdddddddddddddd".toCharArray();
		int highest = 0;
		for (int i = 0; i < chars.length;++i) {
			int count = 1;
			for (int j = i + 1; j < chars.length; ++j) {
				if (chars[i] == chars[j]) {
					++count;
				} else {
					i = j-1;
					break;
				}
			}
			if (count > highest) {
				highest = count;
			}
		}
		System.out.println(highest);

function getLongestConsecutiveChar(str) {
    str = str.split('');
    var maxSequenceLength = 0,
        currentSequenceLength = 1,
        currentChar = str[0],
        maxChar, i;

    for (i = 0; i < str.length; i++) {
        if (currentChar !== str[i + 1]) {
            if (maxSequenceLength < currentSequenceLength) {
                maxChar = currentChar;
                maxSequenceLength = currentSequenceLength;
            }

            currentChar = str[i + 1];
            currentSequenceLength = 1;
        } else {
            currentSequenceLength++;
        }
    }


    return maxChar;
}