Problem:


Score : 500 points

Problem Statement

Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

l_1 + len \leq l_2

S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)

If there is no such integer len, print 0.

Constraints

2 \leq N \leq 5 \times 10^3

|S| = N

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Sample Input 1

5
ababa

Sample Output 1

2

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

Sample Input 2

2
xy

Sample Output 2

0

No non-empty string satisfies the conditions.

Sample Input 3

13
strangeorange

Sample Output 3

5



Sample input:
5
ababa


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

ans = 0
for i in range(n-ans):
    if n - ans > ans:
        for j in range(i+1, n-ans):
            tmp = 0
            if s[i] == s[j]:
                tmp += 1
                ans = max(ans, tmp)
                for k in range(1,n-j):
                    if s[i+k] == s[j+k] and i+k < j:
                        tmp += 1
                        ans = max(ans, tmp)
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
m=n//2
ans=0
l=[]
for i in range(n-1):
  for length in range(1,min(m,n-i)+1):
    if s[i:i+length] in l:
      ans=max(ans,length)
    else:
      l.append(s[i:i+length])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

N = int(input())
S = input()
pd = defaultdict(list)
for i, s in enumerate(S):
    pd[s] += [i]

ans = 0
for value in pd.values():
    if len(value) >= 2:
        ans = 1
        break

if ans == 0:
    print(0)
    sys.exit()
# print(pd)

for i in range(2, N):
    d = defaultdict(list)
    for value in pd.values():
        if len(value) >= 2 and value[0]+i <= value[-1]:
            for v in value:
                ps = S[v:v+i]
                if len(ps) == i:
                    d[ps] += [v]
                
    # print(d)
    
    if len(d) == 0:
        ans -= 1
        for value in pd.values():
            if len(value) == 1:
                continue
            ans += 1
            break
        break
    else:
        pd = d
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

ans = 0
for i in range(1, n//2 + 1):
    d = [0] * (26 ** i)
    for j in range(n - i + 1):
        v = sum([(k+1) * (ord(s[j]) - ord('a')) for k in range(i)])
        d[v] += 1
        if d[v] > 1:
            ans = i
            break
    if ans != i:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
D=dict()

ans=0
for i in range(N//2):
    for j in range(N-i):
        #print(i,j,S[j:j+1+i])
        if S[j:j+i+1] not in D:
            D[S[j:j+i+1]]=j
        else:
            if D[S[j:j+i+1]]<=j-i:
                ans=i+1
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

N = int(input())
S = str(input())

d = defaultdict(list)

for l in reversed(range(1, N+1)):
    i = 0
    while i+l <= N:
        ans = S[i:i+l]
        #print(ans)
        #print(d[ans], type(d[ans]))
        if len(d[ans]) != 0:
            if d[ans][-1]+l <=i:
                print(l)
                sys.exit()
        d[ans].append(i)
        i += 1
print("0")

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
S = input()

ans_max = N//2 + 1

ans = 0
candidate = []
for j in range(N-1):
    if S[j] in S[j+1:]:
        candidate.append(j)

if len(candidate) == 0:
    print(0)
    sys.exit()

ans += 1

for k in range(2, ans_max):
    next = []
    for c in candidate:
        if S[c:c+k] in S[c+k:]:
            next.append(c)
    if len(next) == 0:
        break
    candidate = next
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t=input()
s=[]
for i in range(n):
    s.append(ord(t[i])-96)
now=0
now2=1
plus=0
answer=0
swit=0
save=0
while now<n:
    save=[]
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        else:
            if now2+plus<n:
                if s[now2+plus]==s[now] and not(now2+plus in save):
                    save.append(now2+plus)
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    if save!=[]:
                        now2=save[0]
                        save=save[1:]
                    else:
                        now2+=1
                    plus=0
                    swit=0
            else:
                now2+=1
                plus=0
        if now2+answer>=n+1:
            break
    now+=1
    now2=now+max(answer-1, 1)
    if now+answer>=n+1:
        break
 
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
n=int(input())
s=input()
if n==2:
  if s[0]==s[1]:
    print(1)
  else:
    print(0)
  sys.exit()
l=0;r=n//2+1
while l!=r:
  x=(l+r)//2
  L=[]
  for i in range(n+1-x):
    L.append(s[i:i+x])
  L2=collections.Counter(L)
  if L2.most_common()[0][1]>=2:
    l=x+1
  else:
    r=x
x=l-1
L=[]
for i in range(n+1-x):
  L.append(s[i:i+x])
L2=collections.Counter(L)
L3=[]
c=[]
for i in range(n+1-x):
  L3.append(s[i:i+x])
for i in range(len(L3)):
  if L3[i]==L2.most_common()[0][0]:
    c.append(i)
if max(c)-min(c)>=l-1:
  print(l-1)
else:
  print(l-max(c)+min(c)+1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import defaultdict

n = int(input())

s = input()

sl = set(s)

ans = 0

f = True

if len(s) == len(sl):
    f = False

d = {}
que = []

for i in sl:
    d[i] = []

for i,x in enumerate(s):
    d[x].append(i)

for i in d.values():
    que.append(i)

while f:
    ans += 1
    prev = copy.deepcopy(que)
    que = []

    for x in prev:
        d = defaultdict(list)

        for y in x:
            if y + ans >= n:
                continue
            d[s[y + ans]].append(y)

        for y in d.values():
            if len(y) > 1:
                que.append(y)

    if len(que) == 0:
        break

    if ans + 1 > len(s)//2:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
s_s = list(input())
pos = {}
for i, s in zip(range(n), s_s):
  if s not in pos:
    pos[s] = []
  pos[s].append(i)

ans = 0
for i in range(n):
  start_char = s_s[i]
  cand_pos = pos[start_char]
  valid_cand_pos_index = bisect.bisect_right(cand_pos, i)
  for idx in range(valid_cand_pos_index, len(cand_pos)):
    j = cand_pos[idx]
    k = 1
    while True:
      if j - i <= ans:
        break
      if j + k < len(s_s) and s_s[i + k] == s_s[j + k] and (i + k) < j:
        k += 1
      else:
        break
    if ans < k:
      ans = k

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def do():
    N = int(input())
    S = str(input())
    answer = 0
    for i in range(len(S)-1):
        if answer < len(S)-i:
            for k in range(i+1,len(S)):
                if k+answer <= len(S):
                    if S[i] == S[k]:
                        temp = answer
                        betw = k-i-1
                        if betw+1 > answer:
                            if S[i:i+answer] == S[k:k+answer]:
                                for j in range(betw+1-answer):
                                    if k+j+answer <= (len(S)-1) and S[i+j+answer] == S[k+j+answer]:
                                        temp += 1
                                    else:
                                        break
                        answer = max(answer, temp)
                else:
                    break
        else:
            break
    print(answer)
    
if __name__ == '__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=str(input())

for i in reversed(range(int(N//2))):
    j=0
    for j in range(0,N-i-i):
        buf=S[j:j+i+1]
        if buf in S[i+j+1:]:
            print(i+1)
            break
    else:
        continue
    break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
S = input()
ans = 0
D = Counter(S)
id = 0
dic = {}
for k in D.keys():
    dic[k] = id
    id += 1
m = 0
OB = [-1]*N
for i in range(N):
    if D[S[i]]<=1:
        pass
    else:
        OB[i] = dic[S[i]]
        m = max(m,dic[S[i]])
SSS = [[] for i in range(m+1)]
for i in range(N):
    SSS[OB[i]].append(i)

for n in range(len(SSS)):
    lss = len(SSS[n])
    for i in range(lss):
        for j in range(i,lss):
            ni = SSS[n][i]
            nj = SSS[n][j]
            if i==j or ans>nj-ni or ans>N-nj:
                continue
            id = 0
            while True:
                if nj+id>=N or ni+id>=nj:
                    break
                if S[ni+id]==S[nj+id]:
                    id += 1
                else:
                    break
            ans = max(ans,id)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()

ans=0

for i in range(1,n):
    hm={}
    if i>(n-1)//2:
        break
    for j in range(1,n):
        if j>n-i:
            break
        key=s[j:i+j]
        if key not in hm:
            hm[key]=0
        else:
            ans=max(ans, i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input());S=input();l=[(i,i)for i in range(N)];m=0
while l:
 p,q=l.pop();m=max(m,q-p)
 if q+1<N and S[p:q+1] in S[q+1:]:l.append((p,q+1))
print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
num = [0]*n
for i in range(n):
    if s[i] in s[i+1:]:
        num[i] += 1
        for x in [j for j, x in enumerate(s[i+1:]) if x == s[i]]:
            for y in range(1, 1+x):
                if s[i+1+x-y] == s[i-y]:
                    num[i-y] += 1

print(max(num))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
s = S()



left = 0
right = n//2
flag = 0
while left <= right:
    mid = (left + right) // 2
    str_len = mid
    for sousa_point in range(n - str_len + 1):
        string = s[sousa_point: sousa_point + str_len]
        if s.count(string) > 1:
            left = mid + 1
            flag = 1
            break
    else:
        right = mid - 1
        flag = False


if flag:
    print(mid)
else:
    print(mid - 1)

Submission status: Time Limit Exceeded

Solution code:
def lcs(s1, s2):
    dp = []
    for s2_k in s2:
        bgn_idx = 0
        for i, cur_idx in enumerate(dp):
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if not chr_idx:
                break
            dp[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = s1.find(s2_k, bgn_idx) + 1
            if chr_idx:
                dp.append(chr_idx)
    return len(dp)

N = int(input())
S = input()
ans = 0
for k in range(1,N):
    S1 = S[:k]
    S2 = S[k:]
    tmp_ans = lcs(S1, S2)
    ans = max(ans, tmp_ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(s, k):
    ans=0
    can = set()
    for l in range(n):
        for i in range(len(s) - l):
            a=s[i:i + l + 1]
            if a in can and i>=len(a):
                ans=len(a)                
            can.add(a)
    can = sorted(can)
    print(ans)

n = int(input())
s = input()
solve(s, n)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations


def p_e():
    N = int(input())
    S = input()

    S_idx = defaultdict(list)

    for i in range(N):
        S_idx[S[i]].append(i)

    max_ans = 0
    for c in S_idx.keys():
        if len(S_idx[c]) <= 1:
            continue

        comb_list = list(combinations(S_idx[c], 2))
        i = 1

        f = True
        while f:
            i += 1
            f = False
            for comb in comb_list:
                a = comb[0]
                b = comb[1]
                if a + i - 1 >= N or b + i - 1 >= N:
                    comb_list.remove(comb)
                    continue

                if a + i - 1 >= b:
                    comb_list.remove(comb)
                    continue

                if S[a + i - 1] == S[b + i - 1]:
                    f = True
                else:
                    comb_list.remove(comb)

        if max_ans < i - 1:
            max_ans = i - 1

    print(max_ans)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()

nn=n//2
ans=0

while nn:


    r=nn
    for l in range(n+1-(nn*2)):
        a=s[l:r]
        b=s[r:]
        if a in b:
            ans=nn
            break
        r+=1
    if ans:break
    nn-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
S = str(input())
d = defaultdict(list)
ans = 0
cnt = 0
for i in range(N):
    d[S[i]].append(i)
for x in ("abcdefghijklmnopqrstuvwxyz"):
    for i in range(len(d[x])):
        for j in range(i+1, len(d[x])):
            while S[d[x][i] + cnt] == S[d[x][j] + cnt] and d[x][i] + cnt < d[x][j]:
                cnt += 1
                if d[x][j] + cnt >= len(S):
                    break
            ans = max(cnt,ans)
            cnt = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def search(a,n):
    se = dict()
    data = []
    for i in range(0,len(a)-n+1):
        kkk = a[i:i+n]
        kkk = "".join(kkk)
        if In(kkk,data):
            for j in range(len(se[kkk])):
                if se[kkk][j] <= i-n:
                    return True
            else:
                se[kkk].append(i)
        else:
            bs.insort(data,kkk)
            se[kkk] = [i]
    return False
def solver():
    n = onem()

    s = list(input())
    l = 0
    r = n//2
    for i in range(n):
        mid = -(-(l+r)//2)
        ans = search(s,mid)
        if l == mid:
            break
        if ans:
            l = mid
        else:
            r = mid-1
    print(l)



if __name__ == '__main__':
    solver()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = input()
    slist = list(s)
    sset = set(slist)
    l = []
    lap = l.append
    if len(sset) == n:
        print(0)
    else:
        for i in list(sset):
            lap([j for j,k in enumerate(slist) if k == i])
        pair = []
        pap = pair.append
        for i in l:
            for j in range(len(i)):
                for k in range(j+1,len(i)):
                    pap((i[j],i[k]))
        best = 1
        for i,j in pair:
            x = i
            y = j
            c = 0
            while True:
                if x >= n or y >= n or x >= j or not s[x] == s[y]:
                    break
                c += 1
                x += 1
                y += 1
            best = max([c,best])
        print(best)
    
if __name__ == '__main__':
    main()