CODEWITHSUNDEEP
javastringdynamic-programming
hema begur
hema begur

Reputation: 63

Maximum repeating sequence instead of longest repeating sequence

I am trying to get the most repeated sequence of characters in a string. For example :

Input:

s = "abccbaabccba"

Output:

 2

I have used dynamic programming to figure out the repeating sequence, but this returns the longest repeating character sequence. For example:

Input:

s = "abcabcabcabc"

Output:

2   
2(abcabc,abcabc) instead of 4(abc,abc,abc,abc)

Here is the part of the code where I'm filling the DP table and extracting repeating sequence. Can anyone suggest how I can get the most repeating sequence?

 //Run through the string and fill the DP table.
        char[] chars = s.toCharArray();
        for(int i = 1; i <= length; i++){
            for(int j = 1; j <= length; j++){
                if( chars[i-1] == chars[j-1] && Math.abs(i-j) > table[i-1][j-1]){
                    table[i][j] = table[i-1][j-1] + 1;
                    if(table[i][j] > max_length_sub){
                        max_length_sub = table[i][j];
                        array_index = Math.min(i, j);
                    }
                }else{
                    table[i][j] = 0;
                }
            }               
        }       
        //Check if there was a repeating sequence and return the number of times it occurred.
        if( max_length_sub > 0 ){
            String temp = s;
            String subSeq = "";
            for(int i = (array_index - max_length_sub); i< max_length_sub; i++){
                subSeq = subSeq + s.charAt(i);
            }
            System.out.println( subSeq );
            Pattern pattern = Pattern.compile(subSeq);
            Matcher  matcher = pattern.matcher(s);
            int count = 0;
            while (matcher.find())
                count++;

            // To find left overs - doesn't seem to matter 
            String[] splits = temp.split(subSeq);
            if (splits.length == 0){
                return count;
            }else{
                return 0;
            }
        }

Upvotes: 2

Views: 1615

Answers (1)

user85421
user85421

Reputation: 29680

Simple and dump, the the smallest sequence to be considered is a pair of characters (*):

  • loop over the whole String an get every consecutive pair of characters, like using a for and substring to get the characters;
  • count the occurrence of that pair in the String, create a method countOccurrences() using indexof(String, int) or regular expressions; and
  • store the greatest count, use one variable maxCount outside the loop and an if to check if the actual count is greater (or Math.max())

(*) if "abc" occurs 5 times, than "ab" (and "bc") will occur at least 5 times too - so it is enough to search just for "ab" and "bc", not need to check "abc"

Edit without leftovers, see comments, summary:

  • check if the first character is repeated over the whole string, if not

  • check if the 2 initial characters are repeated all over, if not

  • check if the 3 ...

at least 2 counters/loops needed: one for the number of characters to test, second for the position being tested. Some arithmetic could be used to improve performance: the length of the string must be divisible by the number of repeated characters without remainder.

Upvotes: 1

Related Questions