Find the longest section of repeating characters-CodePudding

Imagine a string like this:

#*****~~~~~~**************~~~~~~~~***************************#

I am looking for an elegant way to find the indices of the longest continues section that contains a specific character. Lets assume we are searching for the * character, than I expect the method to return the start and end index of the last long section of *.

I am looking for the elegant way, I know I could just bruteforce this by checking something like

indexOf(*)
lastIndexOf(*)
//Check if in between the indices is something else if so, remember length start from new 
//substring and repeat until lastIndex reached
//Return saved indices

This is so ugly bruteforce - Any more elegant way of doing this? I thought about regular expression groups and comparing their length. But how to get the indices with that?

CodePudding user response：

Use methods of class Matcher.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {

    public static void main(String args[]) {
        String str = "#*****~~~~~~**************~~~~~~~~***************************#";
        Pattern pattern = Pattern.compile("\\* ");
        Matcher matcher = pattern.matcher(str);
        int max = 0;
        while (matcher.find()) {
            int length = matcher.end() - matcher.start();
            if (length > max) {
                max = length;
            }
        }
        System.out.println(max);
    }
}

The regular expression searches for occurrences of one or more asterisk (*) characters.

Method end returns the index of the first character after the last character matched and method start returns the index of the first character matched. Hence the length is simply the value returned by method end minus the value returned by method start.

Each subsequent call to method find starts searching from the end of the previous match.

The only thing left is to get the longest string of asterisks.

CodePudding user response：

You can do it without regular expressions by manually iterating over the indices of the given string and checking if the previous character matches the current one.

You just need to maintain a couple of variables denoting the start and the end of the longest previously encountered section, and a variable to store the starting index of the section that is being currently examined.

That's how it might be implemented:

public static void printLongestRepeatedSection(String str) {
    if (str.isEmpty()) throw new IllegalArgumentException();

    int maxStart = 0;
    int maxEnd = 1;
    
    int curStart = 0;

    for (int i = 1; i < str.length(); i  ) {
        if (str.charAt(i) != str.charAt(i - 1)) {   // current and previous characters are not equal
            if (maxEnd - maxStart < i - curStart) { // current repeated section is longer then the maximum section discovered previously
                maxStart = curStart;
                maxEnd = i;
            }
            curStart = i;
        }
    }
    
    if (str.length() - curStart > maxEnd - maxStart) { // checking the very last section
        maxStart = curStart;
        maxEnd = str.length();
    }

    System.out.println("Section start: "   maxStart);
    System.out.println("Section end:   "   maxEnd);
    System.out.println("Section:   "   str.substring(maxStart,  maxEnd));
}

main()

public static void main(String[] args) {
    String source = "#*****~~~~~~**************~~~~~~~~***************************#";
    
    printLongestRepeatedSection(source);
}

Output:

Section start: 34
Section end:   61
Section:   ***************************