[Incorrect] Easy O(n) solution NOT using KMP or Z-algorithm


  • 0
    D

    The basic observation is that you can break the string down into chunks of size 2, 3, 4, 5, 6, 7, 8, 9, etc... However, if you can break the string down into chunks of 8 repeated string, you can also break it down into chunks of 2 repeated strings. More generally, if you can break a string down into C chunks, you can break it down into any B chunks, where B is a prime factor of C. Hence we only need to break the string down into a prime number of chunks. Also this is upper bounded by 11, since the product of primes from 2..13 exceeds 10,000.

    class Solution {
    public:
        bool repeatedSubstringPattern(string str) {
            vector<int> blocks = {2, 3, 5, 7, 11};
            if (str.size() < 2) return false;
            for (auto chunks: blocks) {
                if ((str.size() % chunks) != 0) continue;
                const int chunkSize = str.size() / chunks;
                bool same = true;
                for (int i = 0; same && i < str.size() - chunkSize; i += chunkSize) {
                    same = str.substr(i, chunkSize) == str.substr(i + chunkSize, chunkSize);
                }
                if (same) return true;
            }
            return false;
        }
    };
    

  • 2

    It's wrong, fails for example "aaaaaaaaaaaaa" (that's length 13).


  • 0
    D

    @StefanPochmann Ouch - you're right. I shouldn't trust the test cases.


  • 0
    D

    @StefanPochmann Revised logic (since the original logic was totally flawed). Since we're bounded by all lowercase characters, we need only check strings of length 1 through 26 and see if any of them repeat. i.e. no need of going through strings up to n/2, etc...


  • 1

    @dribvurhd Sounds wrong as well. Show the code?


  • 0
    D

    @StefanPochmann ugh (thanks and you're right again!), I had something else in mind, and 26 is definitely not the max. size of a string that can be repeated. Back to the drawing board.


  • 0

    @StefanPochmann Thanks, I've just added your test case.


  • 0

    @1337c0d3r
    Please add "ababababab".
    My wrong solution got accepted just now.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.