Google Interview 686. Repeated String Match

Google Interview 686. Repeated String Match.

Given two strings a and b, return the minimum number of times you should repeat string a so that string b becomes a subscring of sring a.
If b cannot be a substring of a after repeating it, return -1.

String “acb” repeated 0 times is “”, repeated 1 times is “abc” and 2 times is “abcabc”

Example:

• Input a= “a”, b= “aa”
• Result 2 because 0=”” 1=”a” 2=”aa”; 2 is the answer here.

• Input a = “a”, b = “a”
• Result is 1 0 = “” 1 = “a”

Analysis

First check if the strings are the same and return 1
Also check if the string a cannot become a subset of b and return -1.

Repeat string a until string b is a substring.

Test Code

import time
start_time = time.time()
def main():
    print("start")
    

    a = "abcd"
    b = "cdabcdab"

    print ("a: " + a)
    print ("b: " + b)
    
    sol = Solution()
    result = sol.repeatedStringMatch(a,b)
    print("result is: "+ str(result))

    print("end")

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        if not (set(b).issubset(set(a))): return -1
        if b in a: return 1
        
        tmp = a
        count = 1
        for i in range(len(b)//(len(a))+2):
            print("-- in loop i: "+ str(i))
            print("---- in loop step 1 b: "+ b+ "; tmp: "+ tmp)
            if b in tmp:
                print("----- in loop FOUND, b: "+ b+ "; tmp: "+ tmp)
                return count
            tmp += a
            count += 1
            print("---- in loop step 2 b: "+ b+ "; tmp: "+ tmp)
        return -1

if __name__ == "__main__":
    main()
print("--- %s ms ---" % int(((time.time() - start_time)*1000)))

Test Output

start
a: abcd
b: cdabcdab
-- in loop i: 0
---- in loop step 1 b: cdabcdab; tmp: abcd
---- in loop step 2 b: cdabcdab; tmp: abcdabcd
-- in loop i: 1
---- in loop step 1 b: cdabcdab; tmp: abcdabcd
---- in loop step 2 b: cdabcdab; tmp: abcdabcdabcd
-- in loop i: 2
---- in loop step 1 b: cdabcdab; tmp: abcdabcdabcd
----- in loop FOUND, b: cdabcdab; tmp: abcdabcdabcd
result is: 3
end
>>> 

Final Solution Code

def main():
    a = "abcd"
    b = "cdabcdab"

    print ("a: " + a)
    print ("b: " + b)
    
    sol = Solution()
    result = sol.repeatedStringMatch(a,b)
    print("result is: "+ str(result))

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        if not (set(b).issubset(set(a))): return -1
        if b in a: return 1
        
        tmp = a
        count = 1
        while(True):
            if b in tmp:
                return count
            tmp += a
            count += 1
        return -1

if __name__ == "__main__":
    main()