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()

for l in range(N//2, 0, -1):
    for i in range(N-2*l+1):
        target_s = S[i:i+l]
        for j in range(N-2*l-i+1):
            for k in range(l):
                if target_s[k] != S[i+l+j+k]:
                    break
            else:
                print(l)
                exit()
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  N = int(input())
  S = str(input())

  dct = defaultdict(lambda:[N+1,-1])
  for i in range(N):
    for j in range(i+1,N+1):
      dct[S[i:j]][0] = min(dct[S[i:j]][0],i)
      dct[S[i:j]][1] = max(dct[S[i:j]][1],i)

  ret = 0
  for sn in dct.keys():
    if dct[sn][1]-dct[sn][0]>=len(sn):
      ret = max(ret,len(sn))
  return ret

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve(str):

    n = len(str)
    cl = [[0 for x in range(n + 1)]
          for y in range(n + 1)]

    res = ""
    lres = 0

    ind = 0
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):

            if (str[i - 1] == str[j - 1] and
                    cl[i - 1][j - 1] < (j - i)):
                cl[i][j] = cl[i - 1][j - 1] + 1

                if (cl[i][j] > lres):
                    lres = cl[i][j]
                    ind = max(i, ind)

            else:
                cl[i][j] = 0

    if (lres > 0):
        for i in range(ind - lres + 1,
                       ind + 1):
            res = res + str[i - 1]

    return res


if __name__ == "__main__":

    lstr = int(input())
    str = input()
    print(len(solve(str)))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

        l = N // 2
        for i in range(1, l + 1)[::-1]:
            j = 0
            while j + i < N:
                if S.count(S[j:j + i]) >= 2:
                    print(i)
                    exit()
                else:
                    j += 1
        print(0)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

ngram = [defaultdict(lambda : -1) for i in range(N)]

answer = 0
for i in range(N-1, -1, -1):
    # i文字, N
    for j in range(N - i):
        # j文字目から, N
        if ngram[i][S[j:i+j+1]] == -1:
            ngram[i][S[j:i+j+1]] = j
        else:
            if j - ngram[i][S[j:i+j+1]] > i:
                answer = i + 1
                break
    if answer != 0:
        break
print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
save=0
while now<n:
    save=0
    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 save==0:
                    save=now2+plus
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    if save!=0:
                        now2=save
                        save=0
                    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:
N = int(input())
S = input()


def isok(n):
    for i in range(N-2*n+1):
        now = S[i:i+n]
        if S[i+n:].find(now) != -1:
            return True
    return False


left = 0
right = N//2+2

while right - left > 1:
    mid = left + (right-left)//2
    if not isok(mid):
        right = mid
    else:
        left = mid

print(left)

Submission status: Time Limit Exceeded

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

start = {}

for i, s in enumerate(S):
    if s not in start:
        start[s] = []

    start[s].append(i)

max_len = 0
for prefix in start:
    atama = start[prefix]

    for i in range(len(atama)):
        for j in range(i + 1, len(atama)):
            left = atama[i]
            right = atama[j]
            for count in range(N // 2):

                if left + count >= right:
                    break

                if S[left:left+count+1] == S[right:right+count+1]:
                    max_len = max(max_len, count+1)

print(max_len)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
s=input()
flg=False
for i in range(N//2-1,-1,-1):
    # 長さ
    if flg:
        break
    for j in range(0,N-i-1):
        if flg:
            break
        # 開始位置
        tmp=s[j:j+i+1]
        s2=s[j+i+1:]
        if tmp in s2:
            print(len(tmp))
            flg=True
if not flg:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N=int(input())
    S=input()
    ans = 0
    for i in range(N):
        for j in range(i,N):
            t = S[i:j+1]
            if S[j+1:].find(t) >= 0:
                if len(t) > ans:
                    ans = len(t)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
max = 0
for i in range(n):
    for j in range(i, n):
        c = s.count(s[i:j + 1])
        if (c > 1) and (max < len(s[i:(j + 1)])):
            max = len(s[i:(j + 1)])
print(max)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.readline

n = int(input())
s = input()

d = defaultdict(list)

for i in range(n):
    for j in range(i + 1, min(n, i + n // 2) + 1):
        # [i, j)
        d[s[i:j]].append((i, j))

d = sorted(d.items(), key=lambda x: len(x[0]), reverse=True)

for s, lis in d:
    if len(lis) == 1:
        continue
    r = lis[0][1]
    l = lis[-1][0]
    if r <= l:
        print(len(s))
        exit()
print(0)

# print(*d, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import sys

def solve():
    N = int(sys.stdin.readline())
    S = input()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            for ln in range(1, N):
                if i+ln > j:
                    break
                if S[i:i+ln] == S[j:j+ln]:
                    ans = max(ans, ln)
    print(ans)


if __name__ == "__main__":
    solve()

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[i:i+L] in S[i+L:]:
      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:
N = int(input())
S = input()
_S = ''
flag = 0
ans = 0
for i in range(1, N // 2 + 1):  # i文字数取り出す
    for j in range(N + 1 - i):  # j文字目から
        _S = S.replace(S[j:j + i], "")
        if len(_S) < N - i:
            ans = i
            flag = 1
            continue
    if flag == 1:
        flag = 0
        continue

print(str(ans))

Submission status: Time Limit Exceeded

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

# N = 5*10**3
# S = "".join(["t" for n in range(N)])

dp = [{} for i in range(N+1)]

mx = 0

for i in range(N):
#   print(dp)
  for j in range(N):
    if i<j and S[i] == S[j]:
      dp[i+1][j+1] = 1

  for k in dp[i]:
    c_before = dp[i][k]
    if k<N and i+c_before<k and S[k]==S[i]:
      dp[i+1][k+1] = c_before+1
      mx = max(mx,c_before+1)

# print(dp)
print(mx)

Submission status: Time Limit Exceeded

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

max_window_sz = n//2
ans = 0
prev_ans = ans
for i in range(1,max_window_sz+1):
    prev_ans = ans
    for start in range(n-i):
        s1 = s[start+i:]
        s2 = s[start:start+i]
        if(s1.find(s2)!=-1):
            ans = max(i,ans)
            break
    if ans == prev_ans:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def max(a, b):
    return a if a > b else b
 
def is_match(string, pattern):
    # print(string, pattern)
    pat_len = len(pattern)
    skip = [pat_len for _ in range(256)]
    for i in range(pat_len):
        skip[ord(pattern[i])] = pat_len - i - 1
    i = pat_len - 1
    while i < len(string):
        j = pat_len - 1
        while string[i] == pattern[j]:
            if j == 0:
                return True
            i -= 1
            j -= 1
        i = i + max(skip[ord(string[i])], pat_len-j)
    return None


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

    dp = [0] * N

    for i in range(1, N):
        length = dp[i - 1] + 1
        match_string = S[i - length + 1: i + 1]
        matched_string = S[:i+1-length]
        # print(match_string, matched_string)
        if is_match(matched_string, match_string):
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
        # print(dp[i])
    
    # print(dp)
    print(dp[-1])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)
ans=0
for i in range(n-1):
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]
        if len(dic[ss])>=2 and len(ss)>ans:
            ans=len(ss)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(dict)
    ans = 0
    for l in range(N//2, 0, -1):
        t = 0
        for i in range(l):
            t |= 1 << (26*(l-i-1) + ord(S[i])-97)
        d[l][t] = [0, l-1]
        for i in range(1, N-l+1):
            t ^= 1 << (26*(l-1) + ord(S[i-1])-97)
            t = t << 26
            t |= 1 << (ord(S[i+l-1])-97)

            if t not in d[l]:
                d[l][t] = [i, i+l-1]
            else:
                if i > d[l][t][1]:
                    return l
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

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

for i in range(N//2,0,-1):
    for j in range(0,N-2*i+1):
        for k in range(j+i,N-i+1):
            x = S[j:j+i]
            y = S[k:k+i]
            if x == y:
                print(i)
                sys.exit()

print(0)

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)
    flag = False
    for value in pd.values():
        if len(value) >= 2 and value[0]+i <= value[-1]:
            flag = True
            for v in value:
                d[S[v:v+i]] += [v]


    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()
q=[]
for i in range(N):
    for j in range(N):
        if i<j and S[i]==S[j]:
            q.append((i,j,1))
if len(q)==0:
    ans=0
    print(ans)
    exit()
ans=1
while(len(q)>0):
    l1,l2,ln=q.pop()
    if l2+ln<N and l1+ln<l2:
        if S[l1+ln]==S[l2+ln]:
            ans=max(ans,ln+1)
            q.append((l1,l2,ln+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
MAX_INT = int(10e12)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
st = S()

ans = 0
for k in range(1,N):
  s = st[:k]
  t = st[k:]
  dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
  #print(dp)
  for i in range(len(s)):
    for j in range(len(t)):
      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(np.array(dp))
print(ans)

Submission status: Time Limit Exceeded

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

temp = int(n/2)

for j in range(temp):
    for i in range(n-(temp-1)):
        t = s[i:i+temp]
        arr = list(s)
        arr[i:i+temp] = "A"
        arr = "".join(arr)
        if t in arr:
            print(len(t))
            exit()
    temp -= 1
    if temp == 0:
        print(0)
        exit()

Submission status: Time Limit Exceeded

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

h = {}
res = 0
for i in range(len(S)):
  for j in range(i+1, len(S)):
    if j - i + 1 <= res:
      continue
    s = S[i:j+1]
    if s in h and h[s] < i:
      res = j - i + 1
    else:
      h[s] = j

print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
for i in range(n//2,0,-1):
  d = dict()
  for j in range(n-i+1):
    if s[j:j+i] not in d:
      d[s[j:j+i]] = j+i-1
    elif d[s[j:j+i]] < j:
      print(i)
      exit()
print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return sys.stdin.readline().rstrip()
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()

def main():
  n = I()
  s = S()
  ok = 0
  ng = n//2+2
  while ok+1 < ng:
    flag = False
    mid = (ok+ng)//2
    for j in range(n-mid+1):
      if flag:
        break
      for k in range(j+mid, n-mid+1):
        if s[k:k+mid]==s[j:j+mid]:
          flag = True
          break
    if flag:
      ok = mid
    else:
      ng = mid
  print(ok)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
f = False
for i in range(N//2, 0, -1):
    for j in range(N - i):
        x = S[j:j+i]
        if x in S[j+i:]:
            f = True
    if f:
        print(i)
        break
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input().strip()
cntmax = 0
for w in range(1,N//2+1):
    D = {}
    for i in range(N-w+1):
        a = S[i:i+w]
        if a not in D:
            D[a] = []
        D[a].append(i)
    for a in D:
        cur = D[a][0]
        cnt = 10**8
        for i in range(1,len(D[a])):
            cnt = min(cnt,D[a][i]-cur)
            cur = D[a][i]
        if 10**8>cnt>=w:
            cntmax=w
print(cntmax)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N-1):
    for j in range(i+1+ans, N-ans):
        for l in range(ans+1, min(j-i, N-j)+1):
            if S[i:i+l] == S[j:j+l]:
                ans = max(ans, l)
            else:
                break

print(ans)

Submission status: Time Limit Exceeded

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

    max_count = 0

    for i in range(n-1):
        for j in range(i+1, n):
            cur = 0
            while i + cur < j and j + cur < n:
                if s[i+cur] != s[j+cur]:
                    break;
                else:
                    cur += 1

            if max_count < cur:
                max_count = cur

    print(max_count)




resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
dp = [0]*N

for i in range(N):
    j = i+1
    while S[i:j] in S[j:N]:
        dp[i] += 1
        j += 1
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
def acinput():
    return list(map(int,input().split(" ")))


N=int(input())
S=input()
S="?"+S
dp=[[0 for j in range(N+1)]for i in range(N+1)]

for l in range(1,N):
    for r in range(l+1,N+1):
        if S[l]==S[r]:

            dp[l][r]=min(dp[l-1][r-1]+1,r-l)
        else:
            dp[l][r]=0


res=-1
for sdp in dp:
    res=max(res,max(sdp))
print(res)

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-i)//2+1):
    if ans >= j:
      continue
    if s[i:i+j] in s[i+j:]:
      ans = j

print(ans)

Submission status: Time Limit Exceeded

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

A=[['']*N for i in range(N)]

A[0][0]=s[0]


for i in range(1,N):
	A[i][0]=s[i]
	for j in range(i):
		A[i][j+1]=A[i-1][j]+s[i]

ans=0
for i in range(N):
	t=[]
	for j in range(N):
		if A[j][i]!='':
			if A[j][i] not in t:
				t.append(A[j][i])
			else:
				if len(t)-t.index(A[j][i])>=i+1:
					ans=i+1
					break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
l = 0
r = 1
ans = 0
for l in range(N):
    for r in range(l+1, N+1):
        s = S[l:r]
        if S[r:].count(s) < 1:
            continue
        if len(s) > ans:
            ans = len(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
ans = 0
for r in range(N):
  for l in range(r+1):#S[l:r]をS[l+1:]から探す
    for r2 in range(r+1,N):
      dist=r2-r
      length=0
      done=False
      nagasa=min(r,N-1-r)
      for pos in range(nagasa):
        if S[r2-pos]==S[r-pos]:
          length+=1
        else:
          ans=max(ans,length)
          done=True
          break
    if not done:
          ans=max(ans,length)
          done=True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    s = S()
    m = [[0 for i in range(n)] for i in range(n)]
    first = [[INF for i in range(n)] for i in range(n)]
    # set 1st index value
    lcs = 0
    for i, c in enumerate(s):
        # print(c, s[0])
        if c == s[0]:
            m[i][0] = 1
            first[i][0] = i
    # print(m)
    for i in range(1, n):
        for j in range(1, n):
            if i <= j:
                continue
            if s[i] == s[j]:
                if first[i-1][j-1] > j:
                    m[i][j] = m[i-1][j-1] + 1
                    if first[i-1][j-1] == INF:
                        first[i][j] = i
                    else:
                        first[i][j] = first[i-1][j-1]
            else:
                m[i][j] = 0

    # print(m)
    m[0][0] = 0
    print(max(sum(m, [])))


if __name__ == '__main__':
    main()

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)


ans = 0

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

for i in range(1, N):
    ans = max(ans, lcs(S[:i], S[i:]))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def solve():
  N = int(input())
  S = str(input())

  dct = defaultdict(lambda:set([]))
  for i in range(N):
    for j in range(i+1,N+1):
      dct[S[i:j]].add(i)

  for sn in sorted(dct.keys(),key=lambda x:-len(x)):
    if len(dct[sn]) < 2:
      continue
    else:
      if max(dct[sn])-min(dct[sn]) >= len(sn):
        return len(sn)
  return 0

print(solve())

Submission status: Time Limit Exceeded

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

S_dict = {}
for i, s in enumerate(list(S)):
    if s in S_dict:
        S_dict[s].append(i)
    else:
        S_dict[s] = [i]
#print(S_dict)

S_set = set()
for nums in S_dict.values():
    for i, a in enumerate(nums):
        for b in nums[i+1:]:
            S_set.add((a, b))
#print(S_set)
#print("---")

from copy import copy 
for i in range(0, N//2+1):
    tmp_set = copy(S_set)
    for a, b in tmp_set:
        if b+i < N and a+i < b and S[a+i] == S[b+i]:
            pass
        else:
            S_set.remove((a,b))
    #print(S_set)
    if len(S_set) == 0:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

def calc(m):
    for i in range(N-m*2+1):
        a = S[i:i+m]
        for j in range(i+m, N-m+1):
            b = S[j:j+m]
            if a == b:
                return True
    return False

print(bisearch_max(0, N, calc))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
ans = 0
found = False
for l in range(N//2, 0, -1):
    for i in range(N-(2*l)+1):
        target = S[i:i+l]
        if target in S[i+l:]:
            ans = l
            found = True
        if found: break
    if found: break
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()
dp = [[0 for _ in range(n+1)] for _ in range(math.ceil(n/2)+1)]
for k in range(1,math.ceil(n/2)+1):
    s,t = S[:k],S[k:]
    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])
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
def hersCode(n):
  ok = 0
  ng = n
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if nasu(mid):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n):
  global M
  if n <= M:
    return True
  for i in range(N - n * 2 + 1):
    for j in R[S[i]]:
      if i + n > j: continue
      if j + n > N: continue
      t = honya(i, j, n)
      M = max(M, t)
      if t == n:
        return True
  return False

def honya(x, y, n):
  for i in range(n):
    if S[x + i] != S[y + i]:
      return i
  return n

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

R = {}
M = 0
for i in range(N):
  if S[i] not in R:
    R[S[i]] = [i]
  else:
    R[S[i]].append(i)

print(hersCode(N))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

ngram = [defaultdict(list) for i in range(N)]


for i in range(len(S)):
    # i文字, N
    for j in range(len(S) - i):
        # j文字目から, N
        ngram[i][S[j:i+j+1]].append(j)

answer = 0
for i in range(N-1, -1, -1):
    # print(i, ngram[i]), N
    for indexes in ngram[i].values():
        if len(indexes) > 1 and indexes[-1] - indexes[0] > i:
            answer = i + 1
    if answer != 0:
        break
print(answer)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
s=input()

dic=defaultdict(list)

for i in range(n-1):
    for j in range(i+1,n+1):
        ss=s[i:j]
        if dic[ss]==[]:
            dic[ss]+=[j]
            continue
    
        elif max(dic[ss])<=i:
            dic[ss]+=[j]

ans=0
for key,value in dic.items():
    if len(value) <2:
        continue
    if len(value) >=2:
        if len(key) > ans:
            ans=len(key)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
now=0
now2=1
plus=0
answer=0
swit=0
while now<n:
    while now2<n:
        if swit==0:
            if s[now]==s[now2]:
                swit=1
                plus=1
            else:
                now2+=1
        if swit==1:
            if now2+plus<n:
                if s[now+plus]==s[now2+plus] and now+plus<now2:
                    plus+=1
                    if plus>=answer:
                        answer=plus
                else:
                    now2+=1
                    plus=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:
N = int(input())
S = input()

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if S[i] == S[j]:
            equal = 1
            for k in range(1, min(j-i, N-j)):
                if S[i+k] == S[j+k]:
                    equal += 1
                else:
                    break
            ans = max(ans, equal)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getCharNGram(n,s):
    charGram = [''.join(s[i:i+n]) for i in range(len(s)-n+1)]
    return charGram
N = int(input())
S = input()
ans = 0
from collections import Counter
for i in range(1,N//2+1):
    l = getCharNGram(i,S)
    am = Counter(l)
    for j in am.values():
      if j>1:
        ans = i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve():
    n = int(input())
    S = input()
    m = defaultdict(list)
    for i in range(n):
        for j in range(i + 1, i + 1 + n // 2):
            m[S[i:j]].append((i, j))
    ans = 0
    for k, v in m.items():
        if len(v) >= 2:
            if v[0][1] <= v[-1][0]:
                ans = max(ans, len(k))
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    s=input()
    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if s[i:j] in s[j:] and ans < j-i+1:
                ans = j-i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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 S2[:k] in S1:
            ok = k
            k = (k + ng) // 2
        else:
            ng = k
            k = (k + ok) // 2
    ans = max(ans, k)
print(ans)