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.
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.
