p.andrey
BAN USERI'm a veteran, but it made me think a bit of this problem that at first glance can not be done in O (n), yet ...
So, the good news is that it can be done in O(n)... the bad news is that I would not have passed the interview :)), because it took me a while. Today I had a little time and find this idea using KMP. The idea came from the following statement: "the longest prefix which is a good suffix"... exactly what we need.
So, here are the steps:
1. Do the lps table (this is done in O(n)  see KMP algorithm), plus set the oldest parent for each suffix.
2. Rotate all ascending subarrays in the lps table ( O(n) )
3. If the parent for a chr is not 0 then set the lps[chr] = 0 (also done in O(n) ) and for the first char set len(s)  the longest
So, as you can see you need 3 traversal for the initial string no matter how long it is (how big is n)... thus O(3n) = O(n)
Here is an example:
step 1:
s = a b a b a c
lps = 0 0 1 2 3 0
parent = 0 1 0 1 0 6
 this is done in O(n)
step 2:
s = a b a b a c
lps = 0 0 3 2 1 0
parent = 0 1 0 1 0 6
step 3:
s = a b a b a c
lps = 6 0 3 0 1 0
parent = 0 1 0 1 0 6
Done.

p.andrey
January 22, 2019 lexicographic_permutation(arr):
n = length(arr)
len = n  1
p = {0, 1, 2, ..., n1}
while True:
k = len  1
while p[k] > p[k+1]:
k = 1
if k >= 0:
l = len
while p[k] > p[l]:
l = 1
p[k],p[l] = p[l],p[k]
reverse p[k + 1] up to p[n]
for i=0,n do
print(a[p[i]])
else:
break

p.andrey
January 16, 2019 This is how I would do it... some sort of DFS with a little dynamic programming.
So, if for a current vertex that is visited all the path for all adjacent vertices goes T, then all the paths from the current vertex go to T also. If this is done recursively... it should give you the right answer. Basically, if conn[S] == True then NECESSARILY CONNECTED.
connected(v, T)
visited[v] = True
flag = False
for u in adj(v) do
if (u == T) OR // this is the ending vertex, so True
(visited[u] == True AND conn[u] == True) then // this is visited and also the paths from it goes to T
flag = True
if visited[u] == False then
flag = connected(u, T)
// no need to check further...
if flag == False then
break;
conn[v] = flag
return flag
MAIN:
flag = connected(S, T)
if flag == False then
NOT NECESSARILY CONNECTED
else
NECESSARILY CONNECTED

p.andrey
January 11, 2019 Basically, this is a combinatorics problem combined with dynamic programming.
So, compute the delta=sum(MAX)sum(MIN) for all k subsets that can be made and the smallest one is the solution.
Because the array/list is circular, the maximum number of elements that can be used in a subset with the last element from the list is nk, so I used another list b that generates all list that can be made.
Below is the bruteforce approach, but using dynamic programming the complexity can be improved considerably. That is, if a split has been already computed, then there is no need to do it again, instead, first time must be recorded in a table.
Anyway, the complexity of the bruteforce solution below is ~O(k*2^n).
Plus, if the table is implemented as a selfbalancing binary tree(i.e. redblack tree), then the lookup is improved to logarithmic.
subset(S, b, k, sol, min)
if size(S) == k then
if sum(S) <= n then
S[head] = s[head] + (nsum(S))
// we have a candidate solution here (k subsets from list b)
// if the candidate's delta is less than the current known one, then update
delta = do_delta(b, S) // delta does MAXMIN for split S
if delta < min then
min = candidate
sol = S
// now lets generate another solution
// first pop the head of the stack until it can be incremented thus
// to generate another candidate solution
POP(S)
while S[head] >= (nk+1) and head > 0 do
POP(S)
if head > 0 then
S[head] = S[head] + 1
subset (S, b, k, sol, min)
else if sum(S) < n then
PUSH(S, 1) // head = head +1 and S[head] = 1
subset (S, b, k, sol, min)
else
POP(S)
do_dMaxMin(b, k)
let min = infinity // minimum delta: sum(MAX)sum(MIN)
let sol = NIL // the solution (the split)
let S = NIL // a stack
call subset(S, b, k, sol, min)
return (sol, min)
MAIN:
input: let a be the list of numbers
input: let k be the number of subsets
let b be the current list of numbers
let sol to be the best split
let min to be the minimum delta
sol = NIL
min = infinity
b = a
for i=0 to nk do
if i>0 then
// this moves i elements from the beginning of a to the end of it (since a is circular)
b = concat(a[i+1:n], a[1:i])
// lets see the candidate solution
(candidate_sol, candidate_delta) = do_dMaxMin(b,k)
if (candidate_delta < min) then
sol = candidate_sol
min = candidate_delta
return (sol, min)

p.andrey
January 11, 2019 Open Chat in New Window
So, here is the implementation in python:
I see that CLRS cut the string search algorithms from the last edition: KMP, BoyerMoore, and RabinKarp. I also wrote a book (Blueprints of Common Algorithms: A simplified approach to the analysis and implementation of common algorithms) and I didn't include them in it... but it seems that they are needed, so I'm thinking to add them in the next editions.
 p.andrey January 23, 2019