Permutation of the alphabet minimising the number of subsequences to construct a string

user_12534498 0
Viewed 409

There is a special ordering of the alphabet that is different from “abcdefghijklmnopqrstuvwxyz”, that you must determine. You are given a lowercase string with letters ‘a’ through ‘z’, at most 10000 characters long. You are asked to determine the minimum number of times you can repeat this special ordering of the alphabet to produce the given string. Note that when you say the alphabet, you can skip some of the characters (i.e., use a subsequence of the alphabet).

My goal is to efficiently find an optimal ordering of the alphabet, and to count the number of repetitions necessary to produce the given string.

Example: “cdadabcc”

Answer: 4

You get 4 because by reordering the alphabet as:

cdabefghijklmnopqrstuvwxyz

The first time you say the alphabet, you say the first three letters of the special ordering “cdabefghijklmnopqrstuvwxyz”, or “cda”, but skip “b” and the remaining characters. Next time, you skip saying “c” and say “dab”, and then skip the remaining characters. The third time, you say “c” and skip the remaining characters. The last time, you say “c” and skip the remaining characters.

Time; Part of the special alphabet; Total string

1; CDAbefghijklmnopqrstuvwxyz; cda

2; cDABefghijklmnopqrstuvwxyz; cdadab

3; Cdabefghijklmnopqrstuvwxyz; cdadabc

4; Cdabefghijklmnopqrstuvwxyz; cdadabcc

Example 2: “abcdefdeff”

Answer: 3

Rewrite the alphabet as:

abcdefghijklmnopqrstuvwxyz

Time; Part of the special alphabet; Total string

1; ABCDEFghijklmnopqrstuvwxyz; abcdef

2; abcDEFghijklmnopqrstuvwxyz; abcdefdef

3; abcdeFghijklmnopqrstuvwxyz; abcdefdeff

How can I solve this problem? If I can determine the special ordering of the alphabet, it is easy to determine the number of times you need to repeat it to produce the string. To determine this order, I am trying to use dynamic programming and utilize it in a way similar to the longest increasing subsequence problem.

dynamic-programming language-agnostic optimization algorithm string
1 Answers

Let's introduce few terms:

  • Move - two adjacent letters in the input;
  • Jump - a move that is permitted by alphabet;
  • Reset - a move that is not permitted by alphabet;

For example, if alphabet is cba and input is cbacaba:

  • Moves will be: c->b, b->a, a->c, c->a, a->b, b->a;
  • Jumps will be: c->b, c->a & b->a;
  • Resets are: a->c, a->b;

One can easily see that the answer is the number of Resets + 1. Therefore all we care about is whether the Moves that we make are Jumps or Resets.

This allows us to simplify the input - we only care about Moves (pairs of adjacent letters). We can condense the input into a two-dimensional matrix that contains number of each Moves:

For cbacaba:
   a   b   c
a  0   1   1  (a->b & a->c)
b  2   0   0  (b->a x2)
c  1   1   0  (c->a & c->b)

Now we can notice an interesting property of this matrix.

If we chose a letter to be the first letter of the alphabet, then we shall add a sum of that letter's column to the answer, as every Move to that letter is a guaranteed Reset. Additionally the sum of the numbers in the row of that letter will never be added to the answer, as all these Moves are guaranteed Jumps. For example if we take a letter as the first:

  • a: +3 to answer (b->a x2 + c->a), -2 from potential answer. (a->b & a->c)
  • b: +2 to answer (a->b + c->b), -2 from potential answer. (a->b & c->b)
  • c: +1 to answer (a->c), -2 from potential answer. (c->a & c->b)

Now we can choose the best option - which is clearly c, as it removes 2 from the table and adds only 1 to the answer. After we placed the letter on the first place in the alphabet we can treat the problem as if there is no that letter in it whatsoever. For our Moves matrix it means that we simply remove corresponding row and column.

You can repeat this and grow your alphabet one letter at a time until there is no letters left. Picking the letters by Min(Sum(Column) - Sum(Row)). In this case:

   a   b   c
a  0   1   x  (a->b)
b  2   0   x  (b->a x2)
c  x   x   x

Which means that taking a as the next letter will add 2 Resets, and adding b only one. Clearly we should take b and then a which will give us cba as a solution with the total number of Resets being: 1 (from c) + 1 (from b) + 1 (original alphabet) = 3.

Please note I haven't tested the solution and have no intention to.

user_37071250
Related