Longest Uniform Sub-String

Problem Statement

Given a string, find the longest uniform sub-string in it. Return the repeating character and the number of times it repeats.

Solution

Let us take an example string like “abcdddss“. The question is asking us to return the longest sub-string with the same characters. In this case the longest uniform sub-string is “ddd". So, we need to return d as the repeating character and 3 as number of times it repeats.

Approach

1. Declare a hashmap with “Character" as key and "Integer" as value.
2. Declare a variable called “maxx" that will store the length of the longest uniform sub-string. If value of “maxx" remains -1 at the end, then there is no longest uniform sub-string.
3. Store the first character in a variable called “curChar". Iterate the string from second character and store in a variable called “nextChar".
   1. If “curChar" is same as "nextChar", get the count of this character from the hasmap, increment it by 1 and push back into the hashmap.
   2. If this count value is greater than "maxx", then update “maxx".
   3. If “curChar" is not same as “nextChar", then move just forward.
4. Thus we are able to solve this problem in O(n) complexity.

Example Code

Let us write a Java class for this.

public class Sample {    

    public static void main(String[] args) {

        String input = "abcdddss" ;
        Map<Character, Integer> charCount = new HashMap<Character, Integer>();

        char curChar = input.charAt(0);
        int maxx = -1;
        char maxChar = curChar;

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

            char nextChar = input.charAt(i);
            if(curChar == nextChar) {

                int count = 1;
                if(charCount.get(curChar) != null) {

                    count = (int) charCount.get(curChar);
                }

                count = count+1;
                charCount.put(curChar, count);

                if(count > maxx) {

                    maxx = count;
                    maxChar = curChar;
                }
            }
            else {

                curChar = nextChar;

            }

        }// end for

        if(maxx == -1) {
             System.out.println("no longest uniform sub- string");         
        }
       else {
             System.out.println(maxChar + " occurs " + maxx +" times");  
       }        
    }
}

This code returns the following output:

d occurs 3 times