Repeated String Match

Problem

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b​​​​​​ to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
   public:
    int repeatedStringMatch(string a, string b) {
        string s = a;
        int count = 1;
        int maxPossibleRepetions = b.length() / a.length() + 2;
        for (int i = 1; i <= maxPossibleRepetions; i++) {
            int f = s.find(b);
            if (f != -1) return count;
            s = s + a;
            count++;
        }
        return -1;
    }
};