Minimum Lexicographical String after K removals of first, second, last or penultimate characters

Question

Question:

Given a string S S.length() <= 5.10^5 and an integer K K <= S.length(). For each removal, you can:

• Remove the first character of the string
• Remove the second character of the string
• Remove the last character of the string
• Remove the second last character of the string

How can I do exactly K removals such that the final string has minimum lexicographical order?

Example:

S= "abacaaba", K = 2

• Remove the second character of the string
• Remove the second last character of the string

The final string: "aacaaa" which is the smallest lexicographical possible.

P/S:

I've tried for many days but can't figure out an efficience way to solve this problem. But I think there's something to do with dynamic programming.

Answer 1

I will post this answer even though there is an accepted answer because I feel like all the other answers are more complex than they need to be. Below is a O(NK) algorithm that solves this, which can "easily" be made into an O(N) algorithm if a suffix tree is used to do the comparisons of the "middle" portions.

#!/usr/bin/python

def lex_kr(x,K,k_r):
    """
    Get a lexicographically comparable subset of `x` for a given value of
    `k_r`.
    """
    N = len(x)
    assert k_r > 0 and k_r < K # check for corner cases
    k_l = K - k_r
    v_l = min(x[:k_l+1])
    v_r = min(x[-k_r-1:])

    lex = [v_l]
    lex += x[k_l+1:N-k_r-1]
    lex += [v_r]

    return lex

def lex_corner(x,K):
    """
    Get the two lexicographically comparable subsets of `x` for corner cases
    when `k_r=0` and `k_r=K`.
    """
    N = len(x)

    k_l = K
    v_l = min(x[:k_l+1])
    lex0 = [v_l]
    lex0 += x[k_l+1:]

    k_r = K
    v_r = min(x[-k_r-1:])
    lex1 = x[:N-k_r-1]
    lex1 += [v_r]

    return lex0,lex1


def min_lex(x,K):
    subsets = [ lex_kr(x,K,k_r) for k_r in range(1,K) ]
    subsets += lex_corner(x,K) # append the two corner cases
    return min(subsets)

if __name__ == '__main__':

    S = [ x for x in 'abacaaba' ]
    K = 2

    print(min_lex(S,K))

which prints ['a', 'a', 'c', 'a', 'a', 'a'].

The comparisons of the min of the left and right (prefix & suffix) of the arrays can obviously be pre-computed in O(N) time in the function lex_kr.

The middle portion (i.e. x[k_l+1:N-k_r-1]) needs a clever trick to compare lexographically against all other middle portions efficiently. This can be done in O(1) per comparison using a suffix-tree/array as described in other answers (https://cp-algorithms.com/string/suffix-array.html) or a suffix automaton (https://cp-algorithms.com/string/suffix-automaton.html) with the latter being more complex but more efficient. Once implemented, this would yield an O(N) algorithm with less special cases to be checked than other answers.

Answer 2

Here is a (hopefully) mostly complete solution in Python (sorry, I'm even less versed in C++). The idea is I believe the same or very similar to David Eisenstat's, who's answer helped me think more about handling the middles. The comparisons for the middle section use O(1) lookups with O(n log n) preprocessing based on the suffix array construction referenced and linked in the code (David's suggestion is to use O(n) preprocessing and O(1) lookups but I haven't had time to get into O(1) RMQs or Ukkonen's; I'm also charmed by the referenced CP suffix array algorithm). The code includes testing comparing with brute-force but is incomplete in that it does not handle the case where there are only the prefix and suffix and no middle, which should be much simpler to handle anyway. There are probably ways to make the code more succinct and organised but I haven't had time yet to consider it more carefully.

Since we can remove the first, second, penultimate or last characters; the first two letters of the solution will be chosen from two letters (a subsequence) remaining after k or less deletions:

xxxAxxxxxxxB...

Once we've committed to character A by deleting some first characters, we are left only with a choice for B, based on how many deletions we make of the second character. Clearly, we'd like the lowest available character for A, which we may have more than one instance of, and the lowest choice for B after that, for which we also may have more than once instance of.

The suffix is composed similarly, but we need to store the best suffix for each k - num_deletions already chosen for the prefix. Then the final candidate is the lowest two-character-prefix + middle + two-character-suffix, where the middle is fixed by the distribution of deletions in each candidate. We can compare middles using a suffix array or tree with additional information.

Python

def log2(n):
  i = -1
  while(n):
    i += 1
    n >>= 1
  return i

# https://cp-algorithms.com/string/suffix-array.html
def sort_cyclic_shifts(s):
  n = len(s)
  alphabet = 256
  cs = []

  p = [0] * n
  c = [0] * n
  cnt = [0] * max(alphabet, n + 1)

  for i in range(n):
    cnt[ord(s[i])] += 1
  for i in range(1, alphabet):
    cnt[i] += cnt[i-1]
  for i in range(n):
    cnt[ord(s[i])] -= 1
    p[cnt[ord(s[i])]] = i
  c[p[0]] = 0
  classes = 1
  for i in range(1, n):
    if s[p[i]] != s[p[i-1]]:
      classes += 1
    c[p[i]] = classes - 1

  cs.append(c[:])

  pn = [0] * n
  cn = [0] * n
  h = 0

  while (1 << h) < n:
    for i in range(n):
      pn[i] = p[i] - (1 << h)
      if pn[i] < 0:
        pn[i] += n
      
    for i in range(0, classes):
      cnt[i] = 0

    for i in range(n):
      cnt[c[pn[i]]] += 1
    for i in range(1, classes):
      cnt[i] += cnt[i-1]
    for i in range(n-1, -1, -1):
      cnt[c[pn[i]]] -= 1
      p[cnt[c[pn[i]]]] = pn[i]
    cn[p[0]] = 0
    classes = 1
    for i in range(i, n):
      cur = c[p[i]], c[(p[i] + (1 << h)) % n]
      prev = c[p[i-1]], c[(p[i-1] + (1 << h)) % n]
      if cur != prev:
        classes += 1
      cn[p[i]] = classes - 1
    c = cn
    cs.append(c[:])
    h += 1

  return p, cs

# https://cp-algorithms.com/string/suffix-array.html
def suffix_array_construction(s):
  s += "$"
  sorted_shifts, cs = sort_cyclic_shifts(s)
  return sorted_shifts[1:], cs

# https://cp-algorithms.com/string/suffix-array.html
def compare(i, j, l, k, n, c):
  a = c[k][i], c[k][(i+l-(1 << k))%n]
  b = c[k][j], c[k][(j+l-(1 << k))%n]
  if a == b:
    return 0
  elif a < b:
    return -1
  return 1


## MAIN FUNCTION


def f(s, k):
  debug = 0

  n = len(s)

  # Best prefix
  best_first = s[k]
  best_second = s[k+1]
  first_idxs = [k]
  second_idxs = [k + 1]

  for i in range(k - 1, -1, -1):
    if s[i] <= best_first:
      best_first = s[i]
      # We only need one leftmost index
      first_idxs = [i]
  for i in range(k, first_idxs[0], -1):
    if (s[i] < best_second):
      best_second = s[i]
      second_idxs = [i]
    elif s[i] == best_second:
      second_idxs.append(i)

  second_idxs = list(reversed(second_idxs))

  # Best suffix
  # For each of l deletions,
  # we can place the last
  # character anywhere ahead
  # of the penultimate.
  last_idxs = {(n - 2): [n - 1]}
  best_last = s[n - 1]
  for l in range(2, k + 2):
    idx = n - l
    if s[idx] < best_last:
      best_last = s[idx]
      last_idxs[n - 1 - l] = [idx]
    else:
      last_idxs[n - 1 - l] = last_idxs[n - l]

  p, cs = suffix_array_construction(s)

  second_idx = 0

  if debug:
    print(first_idxs, second_idxs, last_idxs)

  while first_idxs[0] >= second_idxs[second_idx]:
    second_idx += 1

  prefix_end = second_idxs[second_idx]
  num_deleted = prefix_end - 1
  remaining = k - num_deleted
  suffix_start = n - remaining - 2
  best = (prefix_end + 1, suffix_start - 1)

  while second_idx < len(second_idxs):
    prefix_end = second_idxs[second_idx]
    num_deleted = prefix_end - 1
    remaining = k - num_deleted
    suffix_start = n - remaining - 2

    len_candidate_middle = suffix_start - 1 - prefix_end

    # The prefixes are all equal.
    # We need to compare the middle
    # and suffix.
    # compare(i, j, l, k, n, c)
    len_best_middle = best[1] - best[0] + 1
    l = min(len_candidate_middle, len_best_middle)

    # Compare middles
    comp = compare(best[0], prefix_end + 1, l, log2(l), n + 1, cs)

    # Candidate is better
    if comp == 1:
      best = (prefix_end + 1, suffix_start - 1)
    elif comp == 0:
      # Compare suffix of candidate with
      # substring at the comparable position
      # of best.
      [last_idx] = last_idxs[suffix_start]
      candidate_suffix = s[suffix_start] + s[last_idx]

      if len_candidate_middle < len_best_middle:
        # One character of best's suffix
        if len_candidate_middle + 1 == len_best_middle:
          to_compare = s[best[1]] + s[best[1] + 1]
        # None of best's suffix
        else:
          idx = best[0] + len_candidate_middle
          to_compare = s[idx] + s[idx + 1]
        # If the candidate suffix is equal
        # to best's equivalent, the candidate
        # wins since it's shorter.
        if candidate_suffix <= to_compare:
          best = (prefix_end + 1, suffix_start - 1)

      elif len_candidate_middle == len_best_middle:
        idx = best[1] + 1
        to_compare = s[idx] + s[last_idxs[idx][0]]
        if candidate_suffix < to_compare:
          best = (prefix_end + 1, suffix_start - 1)

      # len_best_middle < len_candidate_middle 
      else:
        # One character of candidate's suffix
        if len_best_middle + 1 == len_candidate_middle:
          to_compare = s[suffix_start - 1] + s[suffix_start]
        # None of candidates's suffix
        else:
          idx = prefix_end + 1 + len_best_middle
          to_compare = s[idx] + s[idx + 1]

        if candidate_suffix < to_compare:
          best = (prefix_end + 1, suffix_start - 1)

    second_idx += 1

  prefix = s[first_idxs[0]] + s[second_idxs[second_idx-1]]
  middle = s[best[0]:best[1] + 1]
  suffix = s[best[1] + 1] + s[last_idxs[best[1] + 1][0]]

  return prefix + middle + suffix


def brute_force(s, k):
  best = s + "z"
  stack = [(s, k)]

  while stack:
    _s, _k = stack.pop()
    if _k == 0:
      best = min(best, _s)
      continue
    stack.append((_s[1:], _k - 1))
    stack.append((_s[0] + _s[2:], _k - 1))
    stack.append((_s[0:len(_s)-1], _k - 1))
    stack.append((_s[0:len(_s)-2] + _s[-1], _k - 1))

  return best

#    01234567
#s = "abacaaba"
#k = 2

# Test
import random

n = 12
num_tests = 500

for _ in range(num_tests):
  s = "".join([chr(97 + random.randint(0, 25)) for i in range(n)])
  k = random.randint(1, n - 5)
  #print(s, k)
  _f = f(s, k)
  brute = brute_force(s, k)
  if brute != _f:
    print("MISMATCH!")
    print(s, k)
    print(_f)
    print(brute)
    break

print("Done.")

Answer 3

A non-solution failing for abcbaa, K = 2
(Kudos to גלעד ברקן for sharing a test.)

• find the minimum in the first K+1 elements at lowest 0-based index l1
• drop a prefix of length l1 (remove 1st l1 times) - done if l1 = K
• find the minimum in the elements from 1 to 1 + K - l1, inclusive at l2
• "delete" elements from 1 to l2 (if any)(remove 2nd l2 times)
• starting with l3 = 0 and while K - l1 - l2 - l3 > 0,
   remove the larger of the last two elements and increase l3

Answer 4

All together, these ideas should lead to a linear-time algorithm.

If K ≤ N−4, the final string has at least four characters. Its two-character prefix is the least two-character subsequence of the (K+2)-character prefix of the initial string. Compute this prefix and the possible positions of its second character. This can be accomplished in O(K) time by scanning through first K+2 characters, maintaining the least character so far and the least two-character subsequence so far.

Now that we know the two-character prefix, we just have to determine the best suffix. For a prefix that required J deletions to set up, the final string continues with the next N−4 − K characters that we can't touch, followed by the least two-character subsequence of the (K+2 − J)-character suffix of the initial string. We can compute the least two-character subsequence of each of the relevant suffixes using the scanning algorithm described previously. The one tricky part is comparing the untouchable middles efficiently. This can be accomplished with some difficulty using a suffix array with longest common prefixes.

If K > N−4, just return the least (N−K)-character subsequence.

Answer 5

Interesting task!

Update: step 5 incorrect. Here is correct one:

All combinations with length M, which consist of 3'th and 4'th remove operations are equal to this class of operations: Zero or more 3 after that zero or more 4, like this regexp: (3)(4) You can prove it:

1. 43 pair is equal to 33
2. 343 pair equal to 443.
3. Moreover 34...43 is equal to 44...43.

So you can pick rightmost 3 and with rule 3 make it the only one 3. And with rule 4 make transform all left 4 to 3.

any ->rule3-> 4...434...4 -> rule1-> 3...34...4

It leads to O(K^3) complexity of step 6 brute force.

---

Original answer

There are some ideas and solution that works nice in common

1. [More short word is smaller in lexicographical order] Wrong, as @n. 1.8e9-where's-my-share m. mentinoed. All possible results will be equal length (Length-K), because we should use all of them.
2. Lexicographical order means: for semi-length words we match symbols from left to right until it equal. Result of word comparison is result of first different char comparison result. So minimization of i'th symbol is more important than minimization (i+j)'th symbol for all positive j.
3. So most important is first symbol minimization. Only first removal operation can influence on it. By first removal operation we try to place at first place minimal possible value (It will be minimal value from first K symbols). If there is some positions with minimal letter - we will pick leftmost one (we don't want to delete extra symbols and lost correct answer).
4. Now most important is second letter. So we want to minimize it too. We will make it like in 3'th step of algorithm. But, we use 2'nd remove operation and if we had some variants as minimal - we save all of them as candidates.
5. All combinations with length M, which consist of 3'th and 4'th remove operations are equal to only 2 combinations:

• all operations are 4'th: 44...44
• all operations are 4'th but the last one is 3: 44...43. So for every candidate we can check only two possibilities.

6. Brute force all candidates with both possibilities. Find minimal.

In common case this algorithm work's well. But in worst case it's weak. There is counterpoint: Maxlength string with same letter. Then we have K candidates and algorithm complexity will be O(K^2) - it's not good for this task.

For deal with it i think we can choose right candidate at 6'th step of algorithm:

6*. For two candidates - compare their suffix - letters after it. Candidate with smaller letter at same tail position (tail position counts from this candidate head position) is better for our purposes.

7*. Compare two possibilities form 5'th algorithm step and choose minimal.

Problem of this (*) approach - i cannot get a rigid proof that it's better solution. Most hard part, when one candidate is a prefix of another - we compare it letter by letter until smallest doesn't end. for example in string abcabcabc...abc with candidate at first and fourth position.