CODEWITHSUNDEEP
stringalgorithm
Bob
Bob

Reputation: 71

How to determine the smallest common divisor of a string?

I was asked the following question during a job interview and was stumped by it.

Part of the problem I had is making up my mind about what problem I was solving. At first I didn't think the question was internally consistent but then I realized it is asking you to solve two different things - the first task is to figure out whether one string contains a multiple of another string. But the second task is to find a smaller unit of division within both strings.

It's a bit more clear to me now with the pressure of the interview room behind me but I'm still not sure what the ideal algorithm would be here. Any suggestions?

Given two strings s & t, determine if s is divisible by t.
For example: "abab" is divisible by "ab"
But "ababab" is not divisible by "abab".
If it isn't divisible, return -1.
If it is, return the length of the smallest common divisor:
So, for "abababab" and "abab", return 2 as s is divisible 
by t and the smallest common divisor is "ab" with length 2.

Upvotes: 5

Views: 6423

Answers (4)

Surya K
Surya K

Reputation: 1

Here's an answer in python with O(n*m) time complexity:

def divisiblestrs(s: str, t: str)->int:
    if len(t) == 0 or len(s) == 0 or len(t) > len(s) or len(s) % len(t):
        return -1
    i = 0
    while i < len(s):
        if i+len(t) <= len(s) and s[i:i+len(t)] == t:
            i += len(t)
            continue
        break
    if i != len(s):
        return -1
    return 1


if __name__ == "__main__":
    s = "bcdbcdbcdbcd"
    t = "bcdbcd"
    found = False
    for i in range(1,len(t)):
        if divisiblestrs(s, t[:i+1]) == 1:
            print(f"String {t[:i+1]} of {i+1} length is the smallest divisble string between \"{s}\" and \"{t}\"")
            found = True
            break
    if not found:
        print(f"String {s} is not divisible by {t}")

Upvotes: 0

gbansal_g
gbansal_g

Reputation: 1

Here is another attempt at it ....

def check_divisibility(s, t):
    if not len(s): return False
    if s + t != t + s:
        return False
    else:
        return True

if __name__ == "__main__":
    s = "bcdbcdbcdbcd"
    t = "bcdbcd"
    
    found = False
    for i in range(1,len(t)):
        if check_divisibility(s, t[:i]):
            print(f"String {t[:i]} of {len(t[:i])} length is the smallest divisble string between \"{s}\" and \"{t}\"")
            found = True
            break
    if not found:
        print(f"String {s} is not divisible by {t}")

Upvotes: 0

mss
mss

Reputation: 1503

let n is the length of the string s and m is the length of string t, then first we find the gcd(greatest common divisor) of n & m(the largest length that divides both n & m), now we find the all the divisors of gcd in O(square root of gcd) then, we start checking each of them in increasing order whether the starting substring of s or t of length l(divisors of gcd) exist n/l && (m/l) times(using kmp algorithm or robin karp hashing method or rolling hash), if yes, then we break and return length l otherwise we keep checking it until we run out of the divisors and return -1 if nothing is found.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59303

Oddly, you're asked to return -1 unless s is divisible by t (which is easy to check), and then you're only left with cases where t divides s.

If t divides s, then the smallest common divisor is just the smallest divisor of t.

The simplest way to find the smallest divisor of t is to check all the factors of its length to see if the prefix of that length divides t.

You can do it in linear time by building the Knuth-Morris-Pratt search table for t: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

This will tell you all the suffixes of t that are also prefixes of t. If the length of the remainder divides the length of t, then the remainder divides t.

Upvotes: 3

Related Questions