# Leetcode Notes

## 1 random tricks

integer to binary string: bin(324)

sort with multiple keys:

sorted([0,1,2,3,4,5,6,7,8], key=lambda x: (x%3, x))

• ord
• chr

@lru_cache decorator can be used for implementing DP, but looks like I have to use it carefully to always increase the argument:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_recursive(n):


9//2 is same as math.floor(9/2)

• indices = np.argsort(nums)
sorted(range(n), key=cmp_to_key(lambda x,y: x-y))

c = Counter(lst)
c['key']


### 1.1 string functions

'hello'.count('l')
'hello'.index('e')


## 2[A] approaches

### 2.1TODOdynamic programming

#### 2.1.1 (extra-state DP)

This is very good problem. This extends simple DP with

1. two dp variables, i and j
2. one more state variable k

Reference: A good post.

See the following graph:

The first case, directly consume the left k+l a's, and DP on the rest:

$T_l(i,j,k) = T(i+l,j,0) + (k+l)^2$

For each m, consume [i+l:m-1], and DP on rest:

$T_m(i,j,k) = T(i+l,m-1,0) + T(m,j,k+l)$

The l is computed by:

def get_l(i, j):
l = 1
while l <= j-i and boxes[i+l] == boxes[i]:
l += 1
return l


The list of m is computed by:

def get_ms(i, j, l):
res = []
for m in range(i+l,j+1):
if boxes[m] == boxes[i]:
res.append(m)
return res


The full DP logic:

n = len(boxes)
mem = np.zeros((n,n,n), int)
def dp(i, j, k):
# the max point of T[i:j]
if i > j: return 0
if i == j: return (k+1)*(k+1)
if mem[i,j,k] > 0: return mem[i,j,k]

l = get_l(i, j)
res = dp(i+l, j, 0) + (k+l) ** 2

ms = get_ms(i, j, l)
for m in ms:
cand = dp(i+l,m-1,0) + dp(m,j,k+l)
if cand > res: res = cand

mem[i,j,k] = res
return res
# the final output:
dp(0, n-1, 0)


Some tests:

def test():
# 23
removeBoxes([1, 3, 2, 2, 2, 3, 4, 3, 1])
# 9
removeBoxes([1,1,1])


#### 2.1.2 complement's DP

This related, and contains not only one k, but two ks for left and right.

See this post and this.

This actually much easier, and not related to remove boxes at all. But there's one tricky thing to notice: dp(i,j) should indicates the maximum coins we get when we burst all bolloons in [i:j].

def maxCoins(self, nums: List[int]) -> int:
n = len(nums)
mem = np.zeros((n, n), int)
def coins(i, j, k):
return nums[k] * (nums[i] if i>=0 else 1) * (nums[j] if j<n else 1)
def dp(i, j):
# the max coins we get when we burst all bolloons [i:j]
if i > j: return 0
if i == j: return coins(i-1,j+1,i)
if mem[i,j] > 0: return mem[i,j]

cands = []
for k in range(i,j+1):
cand = dp(i, k-1) + dp(k+1, j) + coins(i-1, j+1, k)
cands.append(cand)
res = max(cands)

mem[i,j] = res
return res
return dp(0, n-1)

# 167
maxCoins([3,1,5,8])


#### 2.1.3 complement's DP

See the first discussion in this post. This looks like a number trick, but turns out not. Looks like we have to use DP. There are several tricks:

1. Work on dp(M,K) instead of dp(N,K). I.e. in M moves and K eggs, what is the largest number N of floors we can check.
2. the dp equation is tricky:
dp(m,k) = dp(m-1,k-1) + dp(m-1,k) + 1


We first try dp(m-1,k-1), i.e. one less move, one less eggs, so that we have room for next experiment. So, the first floor we try is dp(m-1,k-1)+1. If it breaks, we use check the lower floors with dp(m-1,k-1). If it doesn't break, we still have k eggs, and we can check dp(m-1,k) more. Thus the equation.

Reference to this post.

import math
import numpy as np
class Solution:
def superEggDrop(self, K: int, N: int) -> int:
mem = np.zeros((N+1,K+1), int)
def dp(m,k):
if m==0 or k==0: return 0
if m==1 and k==1: return 1
if mem[m,k] > 0: return mem[m,k]
res = dp(m-1, k-1) + dp(m-1,k) + 1
mem[m,k] = res
return res
for m in range(N+1):
if dp(m,K) >= N:
return m
assert False

Solution().superEggDrop(1,2)    # 2
Solution().superEggDrop(2,6)    # 3
Solution().superEggDrop(3,14)   # 4
Solution().superEggDrop(2,2)    # 2


#### 2.1.4 Palindromic

This could be the standard reference to Palindromic problems. It is quite clever. Not a lot of discussions, most are pretty bad, except this post. So the idea:

For non-distinct:

• dp(i,j) means the result for S[i:j]
• if S[i] ! S[j]:
• dp(i,j) = dp(i+1,j) + dp(i,j-1) - dp(i+1,j-1)
• i.e. remove the overlap
• if S[i] == S[j]:
• first, same: dp(i,j) = dp(i+1,j) + dp(i,j-1) - dp(i+1,j-1)
• but, with additional: + dp(i+1,j-1) + 1
• so finally: dp(i,j) = dp(i+1,j) + dp(i,j-1) + 1

But non-distinct is not really meaningful. So here's the distince one:

• dp(i,j,a) means number of distinct palindromic bordered by 'a inside S[i:j]
• if S[i] = S[j] = a: very important
• dp(i,j,a) = sum([dp(i+1,j-1,x) for x in a,b,c,d]) + 2
• else: dp(i,j,a) = dp(i+1,j,a) + dp(i,j-1,a) - dp(i+1,j-1,a)

One more thing: the initial value must be -1, otherwise there might be infinite loop!

class Solution:
def countPalindromicSubsequences(self, S: str) -> int:
mod = 10 ** 9 + 7
mem = [[[-1 for _ in range(4)] for _ in range(len(S))] for _ in range(len(S))]
def dp(i,j,a):
if i > j: return 0
elif i == j:
if S[i] == a: return 1
else: return 0

if mem[i][j][ord(a)-ord('a')] >= 0:
return mem[i][j][ord(a)-ord('a')]

# number of distinct pal bordered by 'a inside S[i:j]
if S[i] == S[j] == a:
res = 2
for b in ['a', 'b', 'c', 'd']:
res += dp(i+1, j-1, b)
else:
res = dp(i+1,j,a)
res += dp(i,j-1,a)
res -= dp(i+1,j-1,a)
mem[i][j][ord(a)-ord('a')] = res % mod
return res
res = 0
for a in ['a', 'b', 'c', 'd']:
res += dp(0,len(S)-1,a)
return res % mod


#### 2.1.5 nested DP

This is pretty interesting. Turns out the DP equation is not very difficulty to write.

• dp(day, ntrans) means from 1:day days, up to ntrans transactions, what is the max profit.
• dp(day, ntrans) = max(max([dp(t,ntrans-1) + prices[day] - prices[t] for t in range(day-1)]), dp(day-1,ntrans))

The interesting part:

1. there's a loop in the DP equation
2. the loop actually turns out to be slow, and itself can be calculated using DP, so it is "nested DP"
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# HACK this fails at one test case, even to allocate the memory
if k > len(prices):
res = 0
for i in range(len(prices)-1):
res += max(0, prices[i+1] - prices[i])
return res
mem = [[-1 for _ in range(k+1)] for _ in range(len(prices))]
mem2 = [[None for _ in range(k+1)] for _ in range(len(prices))]
def dp2(t, ntrans):
this = dp(t, ntrans) - prices[t]
if t == 0: return this
if mem2[t][ntrans] != None: return mem2[t][ntrans]
res = max(dp2(t-1, ntrans), this)
mem2[t][ntrans] = res
return res
def dp(day, ntrans):
if day <= 0: return 0
if ntrans == 0: return 0
if mem[day][ntrans] >= 0: return mem[day][ntrans]
# Non-DP solution, TLE at some test cases
# max_tmp = 0
# for t in range(day):
#     tmp = dp(t, ntrans-1)
#     tmp += prices[day] - prices[t]
#     if tmp > max_tmp:
#         max_tmp = tmp
max_tmp = dp2(day-1, ntrans-1) + prices[day]
mem[day][ntrans] = max(max_tmp, dp(day-1, ntrans))
# print(day, ntrans, mem[day][ntrans])
return mem[day][ntrans]
return dp(len(prices)-1, k)
def test():
# 2
Solution().maxProfit(2, [2,4,1])
# 7
Solution().maxProfit(2, [3,2,6,5,0,3])
# 0
Solution().maxProfit(2, [])
Solution().maxProfit(100, l)


#### 2.1.6 FROM take 1 TO how many to take

From this post. The trick is, not thinking about the process of taking slices, but the process of how many slices to take. Here, dp(i,j,k) means from i to j, take k slices, what's the max. There are some additional tricks for this problem:

1. use a invalid condition. The invalid condition is j - i + 1 < k * 2 - 1, k*2 instead of k*3, because we can pick every 2 nodes without problems.
2. the initial is cycle, the that is indicated by cycle variable. Only the initial one is 1, all other are non-cycles (i.e. i and j can be taken at the same time)
3. we only have two branches, to take j or not
class Solution:
def maxSizeSlices(self, A):
def dp(i, j, k, cycle=0):
if k == 1: return max(A[i:j + 1])
if j - i + 1 < k * 2 - 1: return -float('inf')
return max(dp(i + cycle, j - 2, k - 1) + A[j], dp(i, j - 1, k))
return dp(0, len(A) - 1, len(A) // 3, 1)


#### 2.1.7 Other (easy) DP problems

##### 2.1.7.1 (5391) build-array-where-you-can-find-the-maximum-exactly-k-comparisons

The problem is straight forward. I was using peak position and peak value formulation, and it turned out to be complicated. A simpler "prev" just works.

Some tricks:

• the lru_cache(None) is really magick for speeding up
# by minz-2
from functools import lru_cache
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
return dp(-1, n, m, k)

@lru_cache(None)
def dp(prev, n, m, k):
mod = 10**9+7
if n == 0:
if k == 0: return 1
else: return 0
if k < 0: return 0
res = 0
for mi in range(1,m+1):
if prev >= mi:
res += dp(prev, n-1, m, k)
else:
res += dp(mi, n-1, m, k-1)
return res % mod

##### 2.1.7.2(920) number of playlists

The second requirement is ambigious. Other than that, the DP equation is pretty regular. However, two things worth noticing:

1. the initial condition
2. the recursion version is so much slower
class Solution:
def numMusicPlaylists(self, N: int, L: int, K: int) -> int:
mod = 10 ** 9 + 7
mem = np.zeros((N+1, L+1), int)
def dp(n, l):
if l == 0 and n == 0: return 1
if n == 0 and l > 0: return 0
if l == 0 and n > 0: return 0
if mem[n,l] >0: return mem[n,l]
res = dp(n-1, l-1) * n + dp(n, l-1) * max(n-K, 0)
mem[n,l] = res % mod
return mem[n,l]
# return dp(N,L) % mod
#
# ok, this is much faster!!
mem[0,0] = 1
for ni in range(1,N+1):
for li in range(ni,L+1):
mem[ni,li] = (mem[ni-1,li-1] * ni + mem[ni,li-1] * max(ni-K,0)) % mod
return mem[N,L]

Solution().numMusicPlaylists(3,3,1)  # 6
Solution().numMusicPlaylists(2,3,0)  # 6
Solution().numMusicPlaylists(2,3,1)  # 2
Solution().numMusicPlaylists(1,1,0)  # 1

Solution().numMusicPlaylists(16, 16, 4)  # 789741546
Solution().numMusicPlaylists(25, 28, 5)  # 906368459

##### 2.1.7.31386. Cinema Seat Allocation

This is not hard but worth looking at:

1. use 1<<c trick to mark the position
2. use dictionary to record dp solutions
3. for each key not listed, simply +2 for the final solution, to save computation instead of putting inside loop
class Solution:
def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
# 1. sort reserved seats (index by row index)
groups = defaultdict(lambda:[])
for (row, col) in seats:
groups[row].append(col)
def foo(cols):
# 2. calculate: a. (2,3), (4,5), (6,7), (8,9)
gene = sum([1 << col for col in cols])
one = sum(1<<c for c in [2,3,4,5])
two = sum(1<<c for c in [4,5,6,7])
three = sum(1<<c for c in [6,7,8,9])
a = gene & one == 0
b = gene & two == 0
c = gene & three == 0
if a and c: return 2
elif a or b or c: return 1
else: return 0
res = 0
for key in groups:
res += foo(groups[key])
# for all other, +2
return res + (n - len(groups)) * 2


## 3[A] special problems

### 3.1 Number theory

#### 3.1.11363. Largest Multiple of Three

A typical mod-of-3 problem. The trick is to reduce_147 (1 mod 3) or reduce_258 (2 mod 3) either 1 or 2 times.

class Solution:
def largestMultipleOfThree(self, digits: List[int]) -> str:
digits = sorted(digits, reverse=True)
d = {}
for i in range(10):
d[i] = 0
for i in digits:
d[i] += 1
def construct():
res = ''
for i in range(9,-1,-1):
res += str(i) * d[i]
if not res: return res
return str(int(res))
def reduce_258():
if d[2] >= 1: d[2] -= 1
elif d[5] >= 1: d[5] -= 1
elif d[8] >= 1: d[8] -= 1
else: assert False
def reduce_147():
if d[1] >= 1: d[1] -= 1
elif d[4] >= 1: d[4] -= 1
elif d[7] >= 1: d[7] -= 1
else: assert False
if sum(digits) % 3 == 0:
return construct()
if sum(digits) % 3 == 1:
if d[1] + d[4] + d[7] >= 1:
reduce_147()
return construct()
elif d[2] + d[5] + d[8] >= 2:
reduce_258()
reduce_258()
return construct()
else: return ''
if sum(digits) % 3 == 2:
if d[2] + d[5] + d[8] >= 1:
reduce_258()
return construct()
elif d[1] + d[4] + d[7] >= 2:
reduce_147()
reduce_147()
return construct()
else: return ''


### 3.3TODOunion find (29)

This looks interesting

### 3.4TODOtwo pointers

(HEBI: ??) but looks interesting

### 3.5TODOsliding window

Looks like sequence matching

## 4 data structures

### 4.3TODO[A] tree

##### 4.3.0.1 balanced binary search tree

e.g. 1382. Balance a Binary Search Tree. You first sort the array. Then, pick the middle as root and recursively solve the left and right.

class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
# 1. traverse the tree, get an ordered list
# 2. construct a new BST:
#    - find the middle
#    - solve the left/right half
vals = []
def recur(node):
if node == None: return
recur(node.left)
vals.append(node.val)
recur(node.right)
recur(root)
print(vals)
# construct a new BST
def construct(low, high):
if low > high: return None
mid = (high - low) // 2 + low
node = TreeNode(vals[mid])
node.left = construct(low, mid-1)
node.right = construct(mid+1, high)
return node
return construct(0, len(vals)-1)

##### 4.3.0.21361. Validate Binary Tree Nodes

This is a pretty typical problem. The tree is valid if there's no (not necessarily directed) cycle. To do that, traverse the tree from any given point, and record two sets:

• stop: current active given point. Other traversal should stop here.
• done: all visited nodes except the current active stop points.
class Solution:
def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
done = set()
stop = set()
self.flag = True
def visit(item):
# cycle
if item in done:
self.flag = False
return
if item in stop:
stop.remove(item)
def travel(item):
if item == -1: return
l = leftChild[item]
r = rightChild[item]
visit(item)
# early return if cycle
if self.flag:
travel(l)
travel(r)
for i in range(n):
if not i in done and not i in stop:
travel(i)
done.remove(i)
if not self.flag: return False
# separated graph
if len(stop) > 1: return False
# early stoped (should be unnecessary)
if len(done) != n-1: return False
return True


## 5 Tricky problems

### 5.1466. Count The Repetitions (ultra large but repetitive subsequence finding)

Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".

On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

To translate:

def rep(s,n) = s * n S1 = rep(s1, n1) S2 = rep(s2, n2)

This is not DP. It is "repetitive patterns".

First, we are finding s2 inside s1. Thus, we need to first have a map of finding s2 in s1[i:]:

        mem = [None for _ in range(len(s1))]
def fill_mem():
i = 0
for i in range(len(s1)):
idx = i
ct = 0
for c in s2:
idx = (s1+s1).index(c, idx)
if idx + 1 >= len(s1):
ct += 1
idx = (idx + 1) % len(s1)
mem[i] = (idx, ct)

try:
fill_mem()
except Exception as e:
return 0


Then, to save computation, we need to find the repetitive patterns:

For example, we have:

i j ct
0 5 0
5 7 0
7 9 0
9 3 1
3 7 0
7 9 0
9 3 1
3 7 0

Now we found the pattern. It starts from 7, takes one s1, and produces 3 s2.

        def find_circle():
# use that to come up with a repetitive patten
repetitive = set()
# find the circle
i = 0
while True:
if i in repetitive: return i
i, _ = mem[i]
i = i % len(s1)

circle_i = find_circle()


Then, for the circle, we need to get the number of s1 used, and the number of s2 matched:

        def find_circle_t(ci):
i = ci
# number of s1 consumed in the circle
res_from = 0
# number of s2 found in the circle
res_to = 0
while True:
i, c = mem[i]
res_to += 1
res_from += c
if i >= len(s1):
res_from += 1
i = i % len(s1)
if i == ci:
return res_from, res_to

circle_from, circle_to = find_circle_t(circle_i)


Finally, we count s2 in s1 by using the repetitive pattern. The actual number is pretty sensitivie to off-by-one problems.

        # the actual count s2 in s1
count = 1
idx = 0
res = 0
while count <= n1:
if idx == circle_i:
# fast forward
rep = math.floor((n1 - count) / circle_from)
res += rep * circle_to
count += rep * circle_from
# print('fast forward', rep, res, count)
idx, ct = mem[idx]
count += ct
res += 1
# if not matching exactly in the last s1, subtract one because we
# used more
if idx != 0: res -= 1
# use n2 is fairly easy
return math.floor((res - 1) / n2)


Wow, that's a lot of code. It is possible to mix these logic together, but I suspect that would be hard to understand.

Some tests:

def test():
# 2
Solution().getMaxRepetitions("acb", 4, "ab", 2)
# 3
Solution().getMaxRepetitions("abacb", 6, "bcaa", 1)
# 4
Solution().getMaxRepetitions("aaa", 3, "aa", 1)
# 2
Solution().getMaxRepetitions("bacaba", 3, "abacab", 1)
# 0
Solution().getMaxRepetitions("musicforever", 10, "lovelive", 100000)
# 170
Solution().getMaxRepetitions("aaaaaaaaaaaaaaaaa", 10000000, "a", 1000000)


### 5.21366. Rank Teams by Votes

1. use defaultdict
2. use char as dict key
3. +1 instead of pairwise comparison matrix!!
4. sorted with multiple keys (nested tuples in this case)
from collections import defaultdict

class Solution:
def rankTeams(self, votes: List[str]) -> str:
rank = defaultdict(lambda: [0] * n)

# "ABC"
# "BCA"
# "ACB"

for idx, ch in enumerate(vote):
rank[ch][idx] += 1

# d = {"A": [2,0,1],
#      "B": [1,1,1],
#      "C": [0,2,1]}

# !!!
# sorted([((2,0,1),'c'), ((2,0,1),'b'), ((1,1,1),'w')])
ranking = sorted(rank.items(), key=lambda xs: (xs[1], -ord(xs[0])), reverse=True)
return "".join(x for x, _ in ranking)


And compare to my code:

from collections import Counter
from functools import cmp_to_key
class Solution:
def rankTeams(self, votes: List[str]) -> str:
rank = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for i,a in enumerate(alphas):
d[a] = i
for i in range(n):
c = Counter([d[vote[i]] for vote in votes])
for j in range(n):
for k in range(n):
if rank[j][k] == 0:
if c[j] > c[k]:
rank[j][k] = 1
elif c[j] < c[k]:
rank[j][k] = -1

# use the rank
def cmp(x,y):
if rank[x][y] == 0:
return ord(alphas[y]) - ord(alphas[x])
else:
return rank[x][y]
res = sorted(range(n), key=cmp_to_key(cmp), reverse=True)
s = sorted(votes[0], key=lambda x: alphas[i])
return ''.join([s[i] for i in res])


### 5.31371. Find the Longest Substring Containing Vowels in Even Counts

def findTheLongestSubstring(s: str) -> int:
vowels = {'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16}
d, n, r = {0: -1}, 0, 0
for i, c in enumerate(s):
if c in vowels:
n ^= vowels[c]
if n not in d:
d[n] = i
else:
r = max(r, i - d[n])
print(d, i, n, r)
return r


The trick is: scan the string from left to right, and record the current status of even or odd of 'aeiou'.

Or maybe better for understanding:

def encode(l):
res = 0
for i in range(len(l)):
res += l[i] << i
return res
def findsub(s):
status = [0,0,0,0,0]
d = {0: -1}
m = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
res = 0
for i,c in enumerate(s):
if c in m:
status[m[c]] ^= 1
enc = encode(status)
print(status)
if enc not in d:
d[enc] = i
else:
res = max(res, i-d[enc])
return res


Note some tricks:

1. use dict m instead of calling ord and chr
2. status can be just encoded as bits in a number

My bad solution using deque and divide and conquer:

from collections import deque

class Solution:
def findTheLongestSubstring(self, s: str) -> int:
# 1. find the index of aeiou
# 2. merge the index
# I actually don't need to record all indices
qs = [deque() for _ in range(5)]
for i,c in enumerate(s):
if c == 'a':
qs[0].append(i)
if c == 'e':
qs[1].append(i)
if c == 'i':
qs[2].append(i)
if c == 'o':
qs[3].append(i)
if c == 'u':
qs[4].append(i)
# print(qs)
res = 0
mem = []
def recur(qs, start, end):
if start > end: return
for s,e in mem:
if start > s and end < e: return
# modify qs
nonlocal res
for q in qs:
while len(q) > 0 and q[0] < start:
q.popleft()
while len(q) > 0 and q[-1] > end:
q.pop()
# check if even
for q in qs:
if len(q) % 2 == 1:
recur([q.copy() for q in qs], q[0]+1, end)
recur([q.copy() for q in qs], start, q[-1]-1)
mem.append((start, end))
return
res = max(res, end - start + 1)
mem.append((start, end))
recur(qs, 0, len(s)-1)
return res


### 5.45359. Maximum Performance of a Team

See this post. The idea is to first order engineers by efficiency then by speed. Add the first k, keep track of the current efficiency (actually is the current engineer).

Then, swap out the lowest speed with current engineer. Record the max result each time.

Another point is keep an eye on the heapq python library.

import heapq
class Solution:
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
engineers = [(speed[i],efficiency[i]) for i in range(n)]
engineers.sort(key = lambda x : (-x[1],x[0]))
result = 0
heap = []
totalSum = 0
print(engineers)
for i in range(n):
while len(heap) >= k:
totalSum -= heapq.heappop(heap)
result = max(result , (totalSum + engineers[i][0]) * engineers[i][1] )
heapq.heappush(heap,engineers[i][0])
print(heap, result)
totalSum += engineers[i][0]
return result % (10 ** 9 + 7)


### 5.51392. Longest Happy Prefix

This seems to be just KMP (TODO).

An interesting hashing solution in this post:

def longestPrefix(self, s):
res, l, r, mod = 0, 0, 0, 10**9 + 7
for i in xrange(len(s) - 1):
l = (l * 128 + ord(s[i])) % mod
r = (r + pow(128, i, mod) * ord(s[~i])) % mod
if l == r: res = i + 1
return s[:res]