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.

Quick Steps and Scenarios Overview

What You Need to DoQuick Jump
Example:Jump to Step 1
AnalysisJump to Step 2

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()

Helpful Tips

Check all labels, connections, and power ratings before starting so everything fits safely and securely. If any detail looks slightly different on your model, pause the embedded video above for a clear closeup view.


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.