强迫症字符串：寻找最短的“真真串”

强迫症字符串：寻找最短的“真真串”

真真患上了强迫症，比如每天早上都要吃两个包子。

真真发现他对字符串也有强迫症，他喜欢的字符串必须恰好包含3个'z'。 例如'poazdxzz'、'oixzzz'都是真真喜欢的字符串，我们称为真真串。但是像'yuzz'、'deoa'这样的字符串，真真是非常讨厌的。 现在给定一个只包含小写字母的字符串ch，请你帮助真真计算ch的所有子串中，最短的真真串是哪一个。 对于子串，我们规定：“xoi”、“itydre”都是“xoitydre”的子串，但是“xit”不是“xoitydre”的子串。

输入格式

输入一个只包含小写字母的字符串，字符串的长度不超过100000

输出格式

若输入的字符串的所有子串中有真真串，找到最短的真真串，输出其长度。若没有真真串，则输出“zzz”(不包含引号)。

样例 #1

样例输入 #1

happyzazziohell

样例输出 #1

4

样例 #2

样例输入 #2

xoizz

样例输出 #2

zzz

代码1

s = input()
n = len(s)
res = float('inf')
cnt = 0
j = 0
for i in range(n):
    if s[i] == 'z':
        cnt += 1
    while cnt >= 3:
        res = min(res, i - j)
        if s[j] == 'z':
            cnt -= 1
        j += 1

if res == float('inf'):
    print('zzz')
else:
    print(res + 1)

代码2

s = input()
n = len(s)
res = float('inf')
cnt = 0
j = 0
for i in range(n):
    if s[i] == 'z':
        cnt += 1
    if cnt >= 3:
        while s[j] != 'z':
            j += 1
        res = min(res, i - j)
        cnt -= 1
        j += 1

if res == float('inf'):
    print('zzz')
else:
    print(res + 1)

代码3

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
    if cnt[i] >= 3:
        j = i - 1
        while cnt[j] >= 3:
            j -= 1
        res = min(res, i - j - 1)

if res == float('inf'):
    print('zzz')
else:
    print(res)

代码4

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n):
    if cnt[i + 3] > cnt[i]:
        j = i + 1
        while cnt[j + 2] > cnt[i]:
            j += 1
        res = min(res, j - i + 1)

if res == float('inf'):
    print('zzz')
else:
    print(res)

代码5

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n):
    if cnt[i + 3] > cnt[i]:
        for j in range(i + 3, n + 1):
            if cnt[j] - cnt[i] >= 3:
                res = min(res, j - i - 3)
                break

if res == float('inf'):
    print('zzz')
else:
    print(res)

代码6

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i - 1)

if res == float('inf'):
    print('zzz')
else:
    print(res)

代码7

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i + 1)

if res == float('inf'):
    print('zzz')
else:
    print(res - 3)

代码8

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n - 2):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i)

if res == float('inf'):
    print('zzz')
else:
    print(res)

代码9

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n - 2):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i + 1)

if res == float('inf'):
    print('zzz')
else:
    print(res - 2)

代码10

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n - 2):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i)

if res == float('inf'):
    print('zzz')
else:
    print(res + 1)

代码11

s = input()
n = len(s)
res = float('inf')
cnt = [0] * (n + 1)
for i in range(1, n + 1):
    cnt[i] = cnt[i - 1] + (s[i - 1] == 'z')
for i in range(n - 2):
    if cnt[i + 3] > cnt[i]:
        j = i + 3
        while j < n and cnt[j] - cnt[i] < 3:
            j += 1
        if j == n:
            break
        res = min(res, j - i + 1)

print(res if res != float('inf') else 'zzz')