CODEWITHSUNDEEP
javastringtime-complexitybig-ospace-complexity
James Foxwood
James Foxwood

Reputation: 11

Runtime for finding smallest common divisor of 2 strings

I took a stab at this question here: How to determine the smallest common divisor of a string?

I think I have the right implementation, but I'm not sure about the time and space complexities. It seems like it's linear for both. However, the first for-loop check is throwing me off for the time complexity. The StringBuilder is also tricky for the space complexity.

Here's what I coded up:

public static void main(String[] args) {
    String s1 = "bcdbcdbcdbcd", t1 = "bcdbcd";
    String s2 = "bcdbcdbcd", t2 = "bcdbcd";
    String s3 = "lrbb", t3 = "lrbb";
    System.out.println(getLength(s1, t1));
    System.out.println(getLength(s2, t2));
    System.out.println(getLength(s3, t3));
}

private static int getLength(String s, String t) {
    if(s.length() % t.length() > 0)
        return -1;
    StringBuilder sb = new StringBuilder();
    for(int i=0;i*t.length() < s.length();i++) {
        sb.append(t);
    }
    if(!sb.toString().equals(s))
        return -1;
        
    int divisible = 1;
    
    for(int i=1;i<=t.length();i++) {
        
       if(t.length()%divisible++ != 0) {
            continue;
        }
         
        sb = new StringBuilder();
        String subStr = t.substring(0, i);
        while(sb.length() < t.length()) {
            sb.append(subStr);
        }
        if(sb.toString().equals(t))
            return i;
    }
    return -1;
}

Upvotes: 1

Views: 266

Answers (2)

Surya K
Surya K

Reputation: 1

Here's one 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

javadev
javadev

Reputation: 800

Current implementation's complexity:

Let n=|s|, m=|t|

Time:

O(n/m+m^2)

Space:

O(n+m)

Upvotes: 0

Related Questions