Ariel Costas' Blog

How to find repeating patterns in a String using Java

DISCLAIMER: I’m a newbie to Java, I probably didn’t write this in the most efficient way nor following good practices. Feel free to leave a comment suggesting good practices or anything like that!

Let’s say we have a string like “abcabcabcabc” and want to find how many times a pattern repeats on this string. By just observing it, we could see we have the string “abc” repeated 4 times. But how would we implement this in Java? Let’s have a look at this problem and try to solve it.

Premises

Odd numbers

For a string to have a pattern that repeats, the string must be even. So, what we could do is the following:

class FindRepeatingPattern {
    public static int findRepeatingPatternTimes(String input) {
        if (input.length() % 2 != 0) {
            return 1;
        } else {
            // ...the rest of the implementation
        }
    }
}

What we are doing here is check whether the string’s length is even using the modulo operator, “which returns the remainder of a division after one number is divided by another” (Wikipedia). So, if dividing the number by two has any remainder (other than 0), it means the string can’t have a pattern that repeats all over the string.

Finding which lengths can the pattern be

Now we have discarded the even numbers, we can continue with our algorithm. Similarly to before, when we have a pattern, it should repeat itself a number of times, without any extra character. The solution I came along with was to use a for loop, iterating through all the numbers from the length down to 1 (both excluded), and check if that number complies with our needs.

    public static int findRepeatingPatternTimes(String input) {
        int input_length = input.length()

        if (input_length % 2 != 0) {
            return 1;
        } else {
            int i;
            for (i = input_length; i > 1; i--) {
                if (input_length % i == 0) { // Is exact
                    // Do something
                }
            }
        }
    }

So, this is our code right now. I save input.length() to a variable to save function calls, and create a for loop to iterate through all numbers and find which ones are valid. Now, inside this if block, we have to calculate how many substrings we have (in 12 characters with i = 3, we would have 4; as 12 / i = 4);

And now we iterate through the number of substrings to check if they are all equal. If one isn’t, the number will be invalid, so we’ll skip to the next possibility. Once we find a correct value, we can save the number of times it repeats to another variable, which is defaulted to 1 and returned at the end.

Testing

Now we have finished writing our method, it’s time for us to test it. We could just create a main method in our class and call the function a few times with different values, printing the result. But there’s a better way to do it, called Unit Testing . For Java, we do this with a framework called JUnit.

I’m gonna skip the part on how to install it because is quite easy (in my case, using IntelliJ IDEA, you just create a test and the IDE asks if you want to install JUnit with Maven).

How we do the test is by creating another class, for which each method is a test, all annotated with @Test. With the test cases we were given, you would write something like this:

class FindRepeatingPatternTest {
    @Test
    public void firstCase() {
    }

    @Test
    public void secondCase() {
    }
}

And inside, we use a simple assertion and check if the expected value and the one returned by our method is correct, like this:

@Test
public void firstCase() {
        int result = FindRepeatingPattern.findRepeatingPatternTimes("abcabcabcabc");
        assertEquals(4, result);
}

And when running our tests via a terminal, yourIDE or a CI server, they’ll be executed. Note we just call the method directly without instantiating (using new Something()) because we set our method to be static before.

Source code

I’ve uploaded the complete source code for this to a public GitLab Snippet, which can be accessed [through this linkhttps://gitlab.com/-/snippets/2063129).

If you’ve liked this article or found it useful, consider sharing it on social media to help this blog grow!