Skip to content

How to check if string has repeating pattern?

I was recently asked this in an interview question:

Given a input string check if it has repeating pattern and return true or false. For example: "abbaabbaabbaabba" is a repeating pattern of "abba"

private boolean checkPattern(String input) {

}

How can we solve it using regex and also without regex? I am interested in both the approaches with regex and without regex.

Answer

Without regex, you would have to loop through every possible substring of a length that the original string’s length is divisible by, starting from index 0, in the original string and check if it repeats. To check if it repeats, you simply just check every pattern.length() number of characters in the string to see if its the pattern or not. For example, it would look like this,

public boolean checkPattern(String str) {
    String pattern = "";
    for (int i = 0; i < str.length()/2; i++) {
        pattern += str.charAt(i);
        if (str.length() % pattern.length() == 0 && isRepeating(str, pattern)) {
            return true;
        }
    }
    return false;
}

public boolean isRepeating(String str, String pattern) {
    String leftover = str;
    int currIndex = leftover.indexOf(pattern);
    while (currIndex == 0) {
        if(currIndex + pattern.length() == leftover.length()) {
            return true; // you have reached the last possible instance of the pattern at this point
        }
        leftover = leftover.substring(currIndex + pattern.length());
        currIndex = leftover.indexOf(pattern);
    }
    return false;
}

Like user thebjorn mentioned, you can prevent unnecessary calls to isRepeating by only calling it when the string’s length is divisble by the pattern’s length, hence the modulus check in the if statement. Also, the max length a pattern can be for it to repeat in a string is str.length()/2.