Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
3.0k views
in Technique[技术] by (71.8m points)

algorithm - Minimum number of times to repeat sequence of distinct characters to produce given string

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神解答

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...