[SOLVED] The minimum size of substrings for the presence of at least one character

The minimum size of substrings for the presence of at least one character

i have a question that want the minimum length of k that in each consecutive substring of a string with length k, There must be at least one common character.

for example if s="abcaca"

for k = 1 --> substrings are [a], [b], [c] and etc that we can not find a common char in all. for k = 2 --> [ab], [bc], [ca] ... that again there is no a common char in all

but for k = 3 we have [abc], [bca], [cac] [aca] that a and c are in all substrings so answer is k.

or for s="abc" we have k=2 same as above description. my code work correct but its not optimal for large length of s. can anyone solve this with dynamic sliding window or other optimal ways ?

n = input()

queue = list(n)

k = 1
s1 = 0
s2 = 1
last_intersection = None
sub_1 = set(queue[0:1])

while (s2 + k) < len(queue) + 1:
    sub_2 = set(queue[s2: s2 + k])
    if len(sub_2.intersection(sub_1)) > 0:
        sub_1 = sub_2.intersection(sub_1)
        s2 += 1
    else:
        s1 = 0
        s2 = 1
        k += 1
        sub_1 = set(queue[s1: s1 + k])

print(k)

Solution

This can be solved in linear time in the length of the string by finding the minimum of all maximum distances between nearest occurrences of the same character (like also described by user58697).

Here is the implementation:

def solve(s: str) -> int:
    prev_idx, max_dist = {}, {}
    for i, c in enumerate(s):
        max_dist[c], prev_idx[c] = max(max_dist.get(c, 0), i - prev_idx.get(c, -1)), i
    return min(max(d, len(s) - prev_idx[c]) for c, d in max_dist.items())

print(solve("abcaca")) # 3
print(solve("abc"))    # 2
print(solve("bbaaac")) # 3
print(solve("aaab"))   # 2