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:
from collections import defaultdict, Counter
from itertools import combinations
import re

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

d = defaultdict(list)
for i in range(N-3):
  d[S[i:i+5]].append(i)

m = 0
for x in d.values():
  if len(x) > 1:
    for i, j in combinations(x, 2):
      if j < i + 5:
        continue
      l = 5
      while i+l < j and j+l < N and S[i+l] == S[j+l]:
        l += 1
      m = max(m, l)

if m == 0:
  if re.search(r'(....).*(\1)', S):
    m = 4
  elif re.search(r'(...).*(\1)', S):
    m = 3
  elif re.search(r'(..).*(\1)', S):
    m = 2
  elif re.search(r'(.).*(\1)', S):
    m = 1

print(m)

Submission status: Time Limit Exceeded

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

sw=0
for L in range(N-1,0,-1):
  tmp=[]
  for i in range(N-L+1):
    tmp.append([S[i:i+L],i])
  tmp.sort()
  #print(tmp)
  
  old_tmp=tmp[0]
  for i in range(1,N-L+1):
    if tmp[i][0]==old_tmp[0]:
      if tmp[i][1]>=L+old_tmp[1]:
        sw=1
        break
    else:
      old_tmp=tmp[i]
  if sw==1:
    break
print(L if sw==1 else 0)

Submission status: Time Limit Exceeded

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

result = 0

# for a in range(1, N//2+1):
#     for b in range(N-a):
#         s1 = S[b:b+a]
#         for c in range(b+1, N-a+1):
#             s2 = S[c:c+a]
#             if s1 == s2:
#                 result = a


def n_gram(n):
    return[S[idx:idx+n] for idx in range(len(S)-n+1)]


for n in range(1, N//2+1):
    ngram = n_gram(n)
    for string in ngram:
        count = ngram.count(string)
        if count > 0:
            index = [i for i, x in enumerate(ngram) if x == string]
            if min(index) + n - 1 < max(index):
                result = n
                break

print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys; from collections import deque; readline = sys.stdin.readline;

N = int(readline())
S = readline().rstrip()

char2pos = {chr(ord('a') + c): deque() for c in range(26)}


cTopLen = 0

subs = deque()

for index, c in enumerate(S):
    new_subs = deque()

    s1 = deque()
    for pos in char2pos[c]:
        s1.append(pos)
    new_subs.append(s1)

    for i, s in enumerate(subs):
        ns = deque()
        for pos in s:
            _pos = pos + i + 1
            if _pos <= index - (i + 2) and S[_pos] == c:
                ns.append(pos)
        new_subs.append(ns)
        if len(ns) > 0:
            cTopLen = max(cTopLen, i + 2)
    
    subs = new_subs

    char2pos[c].append(index)
    
print(cTopLen)

Submission status: Time Limit Exceeded

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

res = 0

for k in range(1,n//2+1):
    d = [0]*n
    for i in range(n):
        if i+k <= n-1 and s[i] == s[i+k]:
            d[i] = min(k,d[i-1]+1)
            res = max(res,d[i])
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = input()
    m = 0
    for i in range(N+1):
        for j in range(i+1, N+1):
            L_s = j-i
            for k in range(j, N-L_s+1):
                if S[i:j] == S[k:k+L_s]:
                    break
            else:
                break
            if m < L_s:
                m = L_s
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=s[i]
  if d[t]==0:
    d[t]=i
  else:
    ans=max(ans,1)
  for j in range(i+1,n):
    t+=s[j]
    if d[t]==0:
      d[t]=j
    else:
      if d[t]<i:
        ans=max(ans,j-i+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# デバグ

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


try_no = N // 2

ans = 0

for i in range(1, try_no+1):
    for ii in range(N//i+1): 
        chk1 = S[ii:ii+i]        
        
        for iii in range(i+ii, N-i+1):
            chk2 = S[iii:iii+i]
            if chk1 == chk2:
                ans = i
                break
                
        if chk1 == chk2:
            break

print(ans)

Submission status: Time Limit Exceeded

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

se = set(s)
if len(se) == 1:
    print(len(s)//2)
    exit()

suffix = []
for i in range(n):
    suf = s[i:]
    suffix.append((suf, i))

suffix.sort(key=lambda x: x[0])

ans = 0

for l in reversed(range(n//2 + 1)):
    pre = ''
    prei = -1
    for i in range(n):
        if len(suffix[i][0]) < l:
            continue
        suf = suffix[i][0][:l]
        idx = suffix[i][1]
        if pre == '':
            pre = suf
            prei = idx
            continue
        if suf == pre and (idx + l - 1 < prei or prei + l - 1 < idx):
            print(l)
            exit()
        if suf != pre:
            pre = suf
            prei = idx

print(0)

Submission status: Time Limit Exceeded

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

temp = int(n/2)
cnt = temp
check_list = []

for j in range(cnt):
    if n - temp + 1 > ((n - temp*2) + 1) * 2:
        for i in range((n-temp*2)+1):
            t = s[i:i+temp]
            if t in check_list:
                continue
            else:
                check_list.append(t)
            arr = list(s)
            arr[i:i+temp] = "A"
            arr = "".join(arr)
            if t in arr:
                print(len(t))
                exit()
                
        for k in range((n-temp*2)+1):
            if k == 0:
                t = s[-(k+temp):]
            else:
                t = s[-(k+temp):-k]
            if t in check_list:
                continue
            else:
                check_list.append(t)
            arr = list(s)
            if k==0:
                arr[-(k+temp):] = "A"
            else:
                arr[-(k+temp):-k] = "A"
            arr = "".join(arr)
            if t in arr:
                print(len(t))
                exit()
    else:
        for i in range(n-temp-1):
            t = s[i:i+temp]
            if t in check_list:
                continue
            else:
                check_list.append(t)
            arr = list(s)
            arr[i:i+temp] = "A"
            arr = "".join(arr)
            if t in arr:
                print(len(t))
                exit()
    temp -= 1
    check_list = []
    if temp == 0:
        print(0)
        exit()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(input())

for k in range(N//2,1,-1):
  for i in range(N):
    for j in range(i+k,N,1):  
      if j+k <= N:
        if A[i:i+k] == A[j:j+k]:
          print(k); exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
alpha2num = lambda c: ord(c) - ord('a') + 1

N = int(input())
S = input()
S = list(S)

ans = ''
len_ans = 0

alpha = 'abcdefghijklmnopqrstuvwxyz'
alpha = list(alpha)

l = [0] * 27
c = []

#for i in alpha:
#    tmp = [j for j, x in enumerate(S) if x == i]
#    if len(tmp) >= 2:
#        for j in range(len(tmp)):
#            l.append(tmp[j])



for i in range(len(alpha)):
    tmp = [j for j, x in enumerate(S) if x == alpha[i]]
    if len(tmp) >= 2:
        l[i+1] = (len(tmp))
        for j in range(len(tmp)):
            c.append(tmp[j])
c.sort()

#print(l)
#print(c)

t = [0] * 27

ans = []

#print(N)
for i in range(N):
    t = [0] * 27
    for j in range(i, N):
        if t[alpha2num(S[j])] + 1 <= l[alpha2num(S[j])]//2:
            t[alpha2num(S[j])] += 1
            if j == N-1:
                ans.append(''.join(S[i:j+1]))

        else: 
            ans.append(''.join(S[i:j]))
            break

#print(ans)
ans2 = [x for x in set(ans) if ans.count(x) > 1]
#print(ans2) 


ans = 0
for i in range(len(ans2)):
    tmp = len(ans2[i])
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt_m=0
        cnt=0
        for j in range(i,n):
            if s[j-i]==s[j]:
                cnt=min(cnt+1,i)
            else:
                cnt_m=max(cnt,cnt_m)
                cnt=0
        m=max(cnt,cnt_m,m)
    print(m)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
ans=0
d=collections.defaultdict(int)
for i in range(n):
  t=s[i]
  if d[t]==0:
    d[t]=i
  else:
    ans=max(ans,1)
  for j in range(i+1,n):
    t+=s[j]
    if d[t]==0:
      d[t]=j
    else:
      if d[t]<i:
        ans=max(ans,j-i+1)
print(ans)

Submission status: Time Limit Exceeded

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

i = n // 2

while 0 < i:
	j = 0
	f = False
	
	while j < n - i:
		if s[j:j+i] in s[j+i:n]:
			f = True
			break
		j += 1
	
	if f == True:
		break
	
	i -= 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    def input():
        return sys.stdin.readline()[:-1]
    N = int(input())
    S = [ord(x) for x in input()] + [-1]
    ans = 0
    s = -1
    while s < N-1-ans*2:
        s += 1
        for e in range(s+ans+1,N-ans):
            if S[s] == S[e]:
                k = 0
                while s+k < e and e+k < N and S[s+k] == S[e+k]:
                    k += 1
                ans = max(ans,k)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
n = int(input())
s = input()
count = 0
ans = 0
for i in range(n):
    for j in range(n-i):
        if s.count(s[i:i+j]) >= 2 and len(s[i:i+j])>=1:
            count = j
            ans = max(count,ans)
print(ans if ans <= n//2 else n//2)

Submission status: Time Limit Exceeded

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


def main():
    def search(s, t):
        if len(t) > len(s):
            return 0
        for i in range(len(s) - len(t) + 1):
            if s[i:i + len(t)] == t:
                return 1
        return 0

    ans = 0
    for i in range(1, N):
        S1 = S[:i]
        S2 = S[i:]
        ok = 0
        ng = len(S2) + 1
        k = (ok + ng) // 2
        while ng - ok > 1:
            if search(S1, S2[:k]):
                ok = k
                k = (k + ng) // 2
            else:
                ng = k
                k = (k + ok) // 2
        ans = max(ans, k)
        if ans > N - i - 1:
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(n, mid, s, suffix):
    # print(mid, s, suffix)
    tmp = "A" + s[:mid-1]
    for i in range(n - mid + 1):
        # tmp = (s[i:i+mid], i)
        tmp = tmp[1:] + s[i+mid-1]

        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tgt.startswith(tmp):
                if int(tgt[-9:]) >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    # suffix.append((s[i:], i))
    suffix.append(s[i:] + "{:0>10}".format(i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(n, mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(n, mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

import bisect

N = int(input())
s = input().split() 
s = list(s[0])
alf_i = [[] for _ in range(26)]

for i in range(N):
    alf_i[ord(s[i])-97].append(i)


ans=0
for i in range(N):
    x = bisect.bisect_left(alf_i[ord(s[i])-97], i)
    for j in range(x+1,len(alf_i[ord(s[i])-97])):
        y = alf_i[ord(s[i])-97][j]
        cnt=0
        while y+cnt<N and s[i+cnt]==s[y+cnt]:
            if i+cnt==y:
                break
            cnt+=1
        ans = max(cnt,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

def get_keys_from_value(d, val):
    return [k for k, v in d.items() if v == val]

n = INT()
s = input()

di = {}
ans=0

for start in range(n):
    for end in range(start,n):
        di[(start,end)] = s[start:end+1]

for k,v in di.items():
    tmp = di[k]
    di[k]=0
    if tmp in di.values():
        keys = get_keys_from_value(di,tmp)
        for i in keys:
            if k[1]<i[0]:
                ans = max(ans,len(tmp))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC141 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
S = input()
ans = 0
for k in range(1,n):
    s,t = S[:k],S[k:]
    dp = [[0 for _ in range(n-k+1)] for _ in range(k+1)]
    for i in range(k):
        for j in range(n-k):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j+1],dp[i+1][j])
    ans = max(ans,dp[-1][-1])
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in range(1, N):
        if s[i:i+j] in s[i+j:]:
            tmp = j
            if tmp > ans:
                ans = tmp

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 len(s_s) - j <= 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:
# デバグ

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


try_no = N // 2

ans = 0

for i in range(1, try_no+1):
    for ii in range(N//i+1): 
        chk1 = S[ii:ii+i]        
        
        for iii in range(i+ii, N-i+1):
            chk2 = S[iii:iii+i]
            if chk1 == chk2:
                ans = i
                break

print(ans)

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)

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

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        S = input().rstrip()

        half = N // 2
        for length in range(1, half + 1)[::-1]:
            i = 0
            already = set()
            while i + length < N:
                v = S[i:i + length]
                if v in already:
                    i += 1
                    continue

                if S.count(S[i:i + length]) >= 2:
                    print(length)
                    exit()
                else:
                    already.add(v)
                    i += 1
        print(0)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
N = input()
S = input()
count = 0
for i, s in enumerate(S):
  for j in range(len(S)-i):
    cha = S[i:i+j]
    s1 = S.replace(cha, "", 1)
    if cha in s1:
      if count < j:
        count = j
print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n=int(input())
  s=input()
  
  t=[s[i:] for i in range(n)]
 
  for w in range(n//2,0,-1):
    for i in range(n-w):
      if s[i:i+w] in t[i+w]:
        print(w)
        quit()
 
  print(0)
 
 
if __name__ == '__main__':
  solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
f1 = False
t = dict()
for z in range(n):
    t[s[z]] = t.get(s[z],0) + 1
    if t[s[z]] >= 2:
        f1 = True
        break

for i in range(n//2,1,-1):
    #for j in range(n-2*i+1):
    w = set()
    for j in range(n-2*i,-1,-1):
        #for k in range(j+i,n-i+1):
        for k in range(n-i,j+i-1,-1):
            w.add(s[k:k+i])
            if s[j:j+i] in w:
                    print(i)
                    exit(0)    
if f1:
    print(1)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
n=int(input())
s=input()
count=0
for le in range(1,n-1):
    mojiretu=defaultdict(tuple)
    for i in range(n-le+1):
        j=i+le
        if mojiretu[s[i:j]]:
            if j <= mojiretu[s[i:j]][0] or mojiretu[s[i:j]][1]<=i:
                count=max(count,j-i)
        else:mojiretu[s[i:j]]=(i,j)
# while True:
#     for i in range(n)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def check(num, s, left, right):

    if right - left <= 1:
        print(left)
        sys.exit()

    half = (left + right) // 2

    # print(half, left, right)

    for i in range(num - half):
        now_str = s[i]

        for j in range(i + half, num):
            if half >= num - j + 1:
                break

            if now_str == s[j]:
                i_ind, j_ind = i, j

                for k in range(half - 1):
                    i_ind += 1
                    j_ind += 1
                    if i_ind >= j or j_ind >= num:
                        break
                    if s[i_ind] != s[j_ind]:
                        break
                else:
                    check(num, s, half, right)
    check(num, s, left, half)

def main():
    num = int(input())
    s = list(input())

    left, right = 0, num

    check(num, s, left, right)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S.count(S[i:i+L]) >= 2:
      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from array import array

N = int(input())
S = array('u', list(input()))

s2 = len(S)-1

len_deque = deque([])


def len_common_substring(s1, s2):
    l = 0
    _s1 = s1
    _s2 = s2
    while(_s2 < len(S) and _s1 < s2):
        if S[_s1] == S[_s2]:
            l += 1
        else:
            return l
        _s1 += 1
        _s2 += 1
        #print(_s1, _s2)
    return l


def len_longest_common_substring_starts_with_s2():
    s1 = s2-1
    longest = 0
    while(s1>=0):
        if S[s1] == S[s2]:
            longest = max(longest, len_common_substring(s1, s2))
        s1 -= 1
    return longest

while(s2>=0):
    l = len_longest_common_substring_starts_with_s2()
    len_deque.append(l)
    s2 -= 1
    

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

len_list = list(len_deque)
len_list.sort()
print(len_list.pop())

Submission status: Time Limit Exceeded

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

for l in range(N//2, 0, -1):
    tried = set()
    for i in range(N-2*l+1):
        part = S[i:l+i]
        if part in tried:
            continue
        tried.add(part)
        for j in range(l+i, N-l+1):
            cmp = S[j:j+l]
            if cmp == part:
                print(l)
                import sys
                sys.exit()
    del tried
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
for i in range(N):
    for j in reversed(range(i + 1, (N // 2) + 1)):
        k = S[i:j+1]
        if k in S[:i]:
            if len(k) > ans:
                ans = len(k)
        if k in S[j+1:]:
            if len(k) > ans:
                ans = len(k)
print(ans)

Submission status: Time Limit Exceeded

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

# 文字とindexのマップ
dic = {}
for i, n in enumerate(S):
    if n not in dic:
        dic[n] = [i]
    else:
        dic[n].append(i)


ret_max = 0
for i in range(N):
    index = []
    temp_max = 0
    for j in range(N):
        # target = S[i:j + 1]
        target = S[i]

        if target in dic:
            idx_lst = dic[target].copy()
            # print(idx_lst, i, target)

            idx_lst.remove(i)

            if idx_lst:
                temp_max = 1
            else:
                temp_max = 0
        else:
            continue

        cnt = 1
        if idx_lst:
            next_idx = idx_lst[0]
        else:
            next_idx = 0
        while idx_lst:
            for idx in idx_lst:
                if j + 1 + cnt <= next_idx and S[idx:idx + 1 + cnt] == S[i:j + 1 + cnt] and idx + 1 + cnt <= N:
                    # print(idx, S[idx:idx + 1 + cnt], S[i:j + 1 + cnt])
                    temp_max = 1 + cnt
                else:
                    idx_lst.remove(idx)

            cnt += 1

        ret_max = max(ret_max, temp_max)


print(ret_max)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = ns()

dic = {}
strs = set()

for st in range(n):
    stri = s[st]
    if not stri in strs:
        dic[stri] = [st, -1]
        strs.add(stri)
    else:
        dic[stri][1] = st

    for ed in range(st+1, min(st+n//2+2, n)):
        stri += s[ed]
        if not stri in strs:
            dic[stri] = [st, -1]
            strs.add(stri)
        else:
            dic[stri][1] = st

strlist = list(strs)
strlist.sort(key=lambda x: len(x), reverse=True)
ans = 0
for stri in strlist:
    val = dic[stri]
    leng = len(stri)
    if val[1] - val[0] >= len(stri):
        ans = len(stri)
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ss = input()

    for k in reversed(range(1, N//2+1)):
        strs = []
        for L in range(N-k+1):
            R = L+k-1
            ss = Ss[L:R+1]
            strs.append((ss, L, R))

        ds = dict()
        for ss, L, R in strs:
            if ss not in ds:
                ds[ss] = [(L, R)]
            else:
                ds[ss] += [(L, R)]

        for ss, LRs in ds.items():
            maxL = -1
            minR = N
            for L, R in LRs:
                if L > maxL:
                    maxL = L
                if R < minR:
                    minR = R
            if minR+1 <= maxL:
                return k

    return 0

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.array([[0] * (N + 1)] * (N + 1))
# for i in range(N):
#     dp[i][0] = 0
# for j in range(N):
#     dp[0][j] = 0

for i in range(1, N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        # elif dp[i - 1][j] >= dp[i][j - 1]:
        #     dp[i][j] = dp[i - 1][j]
        # else:
        #     dp[i][j] = dp[i][j - 1]
print(dp.max())

Submission status: Time Limit Exceeded

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

nn=n//2
ans=0


def solve(nn):
    r=nn
    for l in range(n+1-(nn*2)):
        a=s[l:r]
        b=s[r:]
        if a in b:
            print(nn)
            exit()
        r+=1
    return 0



while nn:

    solve(nn)
    nn-=1

print(ans)

Submission status: Time Limit Exceeded

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

def check(L):
  for i in range(N - (L * 2) + 1):
    if S.count(S[i:i+L]) >= 2:                                                      return True
  return False

left = 0
right = N // 2 + 1
while right - left > 1:
  mid = left + (right - left) // 2
  if check(mid):
    left = mid
  else:
    right = mid
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

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

dp = np.array([[0] * (N + 1)] * (N + 1))
for i in range(N):
    dp[i][0] = 0
for j in range(N):
    dp[0][j] = 0

for i in range(1, N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        # elif dp[i - 1][j] >= dp[i][j - 1]:
        #     dp[i][j] = dp[i - 1][j]
        # else:
        #     dp[i][j] = dp[i][j - 1]
print(dp.max())

Submission status: Time Limit Exceeded

Solution code:
from itertools import count

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

abc = 'abcdefghijklmnopqrstuvwxyz'

T = ['']

flag = True
for i in count():
    T2 = T[:]
    T = []
    for t in T2:
        for c in abc:
            if S.count(t + c) > 1:
                T.append(t + c)
                flag = False
    if flag:
        print(i)
        break
    flag = True

Submission status: Time Limit Exceeded

Solution code:
def longest_match(left, right):
    table = [[0 for _ in range(1 + len(right))] for _ in range(1 + len(left))]
    for i in range(len(left)):
        for j in range(len(right)):
            if left[i] == right[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = max(table[i+1][j], table[i][j+1])
    return table[-1][-1]

def solve(N, S):
    longest = 0
    for i in range(1, N):
        left = S[:i]
        right = S[i:]
        longest = max(longest_match(left, right), longest)
    return longest

def main():
    N = int(input().strip())
    S = input().strip()
    result = solve(N, S)
    print(result)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
dic = {}
for i in range(n):
    for j in range(i+1,n+1):
        t = s[i:j]
        if t not in dic:
            dic[t] = []
        dic[t].append(i)
ans = 0
for k,v in dic.items():
    if len(v) < 2:
        continue
    l,r = v[0], v[-1]
    if l+len(k)-1 < r:
        ans = max(ans, len(k))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(min(j - i, N - j + 1) + 1):
            if S[i : i + k] == S[j : j + k] :
                pass
            else:
                break
            l = max(l,  k)     
print(l)

Submission status: Time Limit Exceeded

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

res = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        tt = res
        mx = min(j - i, n - j)
        if tt >= mx:
            continue
        while tt <= mx:
            tt += 1
            if s[i:i + tt] != s[j:j + tt]:
                break
        _res = tt - 1
        res = max(res, _res)

print(res)

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
                swit=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 copy

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

c = []
find = []
for i in range(N//2+1):
    new_c = copy.deepcopy(c)
    for k in c:
        v = k+S[i]
        if v in S[i+1:]:
            find.append(len(v))
        new_c.append(v)
    if S[i] not in c:
        if S[i] in S[i+1:]:
            find.append(1)
        new_c.append(S[i])
    c = new_c
if len(find)>0:
    print(max(find))
else:
    print(0)