Finding Special Parts in a Word

Question

Task description:

Imagine you have a long word made up of small letters like "a", "b", "c", ancd so on. Let’s call this word a puzzle word.

We want to look at all the smaller parts (called substrings) of this word. A substring just means some letters that are right next to each other in the word.

Now here’s the challenge: Count how many special parts are hiding inside this puzzle word!

A part is special if it follows one of these rules:

It’s 2 letters long, and both letters are the same. Example: "aa" is special, "ab" is not.

It’s 3 or more letters long, and:

It starts and ends with the same letter

All the letters in the middle are exactly the same letter

Example: "xyyx" is special → it starts and ends with "x", and the middle is just "yy"

Example: If the puzzle word is "xyyx":

Let’s check some parts:

"xy" → Not special

"yy" → Yes! both letters are the same

"xyyx" → Yes! starts and ends with "x", middle is just "y"

So the answer is 2 special parts.

Things to remember: The puzzle word will only have lowercase letters.

The word can be very long, up to 300,000 letters!

Here is my code:

import java.util.*;
class Main {

    public static long special(String word) {
        int n = word.length();
        long count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int len = j - i + 1;
                String sub = word.substring(i, j + 1);

                if (len == 2) {
                    if (sub.charAt(0) == sub.charAt(1)) {
                        count++;
                    }
                } else if (len > 2) {
                    if (sub.charAt(0) == sub.charAt(len - 1)) {
                        // Check if middle part has exactly 1 distinct character
                        Set<Character> middleChars = new HashSet<>();
                        for (int k = 1; k < len - 1; k++) {
                            middleChars.add(sub.charAt(k));
                            if (middleChars.size() > 1) break;
                        }
                        if (middleChars.size() == 1) {
                            count++;
                        }
                    }
                }
            }
        }

        return count;

    }

    public static void main(String[] args) {
        System.out.println(special("xyyx"));    // Output: 2
        System.out.println(special("aabbaa"));  // Output: 4
        System.out.println(special("pq"));      // Output: 0
    }
}

My code runs in time complexity of O(n^2 * m) where n is the input word length and m is the substring string length. I am looking for an algorithm that takes less than O(n^2)

I need help in finding a way to solve this in less time complexity.

Answer 1

The "length 2" rule is unnecessary, just ignore it and read the "length ≥ 3" rule as "length ≥ 2" instead. You can simplify your code accordingly, removing the if (len == 2) { ... }, not checking the length, and checking if the middle part has at most 1 distinct character.

Anyway, no need to go over the data multiple times. Just go over it once, and at each letter, add how many special parts end there with that letter. For that, it's enough to remember the current streak of equal letters (its letter and length) and the letter preceding that streak.

    public static long special(String word) {
        long specials = 0;
        char streakLetter = '-', letterBeforeStreak = '-';
        int streakLength = 0;
        for (char letter : word.toCharArray()) {
            if (letter == streakLetter) {
                specials += streakLength++;
            } else {
                if (letter == letterBeforeStreak)
                    specials++;
                letterBeforeStreak = streakLetter;
                streakLetter = letter;
                streakLength = 1;
            }
        }
        return specials;
    }

This takes O(n) time.

Attempt This Online!

Answer 2

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int len = j - i + 1;
            String sub = word.substring(i, j + 1);

You should always look at the source code of library methods before you use them to see what they do. That way you get a lot fewer nasty surprises when the code does something you didn't expect. The substring method creates a copy of the char array that is backing the String and then creates a new String object for it. For a 300000 character input string these four lines create 89999700000 extremely short lived String and char array objects. This math should stop you right on your tracks and force you to look for a different approach instead of using time on a dead end solution.

This problem is probably one of those where you should try to solve it manually with pen and paper first, trying to act like a human instead of thinking how a compute might do it, and examine how you behaved while doing it. Did you start from the first letter and go through the whole String and then go back to start and continue from the second letter? I suspect not.

Answer 3

In such code, one should look for rules, smart logic. Here we have sequences x² and xyⁿx. (As already said in an earlier answer, with n = 0 one covers the first sequence.)

The logic here is detecting a sequence of the same character. And that is the trick: the rest is of secundary interest.

After every sequence of 0-n chars xxxx I check a nesting

// x²
// xyⁿx
public static long special(String word) {
    int n = word.length();
    long count = 0;

    for (int i = 0; i < n;) {
        char chi = word.charAt(i);
        int starti = i;
        ++i;
        while (i < n && word.charAt(i) == chi) {
            ++i;
        }
        int len = i - starti;
        if (len == 2) {
            ++count;
        }
        if (i + 1 < n) {
            char chj = word.charAt(i);
            starti = i;
            ++i;
            while (i + 1 < n && word.charAt(i) == chj) {
                ++i;
            }
            if (word.charAt(i) == chi) {
                ++count;
                len = i - starti;
                if (len == 2) {
                    ++count;
                }
            }
        }
    }
    return count;
}

This is O(n) as the index i is only advanced. The code stays very near to the data, only inspecting the next character.

It is not wrong to consider using Set, substring and maybe indexOf, but here it only lengthens the code.

There is a disadvantage to this style of low level coding: you must ensure all details do what is intended: here there is no ++i inside the for and one compares i + 1 < n.

Note that I do not use a second index j but keep the old i in starti (in order to calculate the length). That makes the code more understandable.

As final nicety you could introduce a function to detect a sequence of same characters, doing the inner whiles. Especially do such things when you introduce a class (WordPart?).

---

Addition

Mentioned (commented) is that "aaaa" is also special, hence my solution is not correct. So: "[aa][aa]" and "a[aa]a".