GetSubsequence
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett · Dynamic Programming
Problem Statement
Problem Statement
Given a String s, we will first collect all distinct positive length subsequences of s, and place them in a list L. A subsequence of s is obtained by deleting 0 or more characters. Next, sort L into ascending order by length. Where ties occur, break them lexicographically. Here uppercase letters occur before lowercase letters. Finally, return the String in position pos % k (0-based), where k is the number of elements in L, and % is the modulus operator.
Constraints
- s will contain between 2 and 50 characters inclusive.
- Each character in s will be a letter ('A'-'Z','a'-'z').
- pos will be an integral value between 0 and 2^63 - 1 inclusive.
- pos will not have extra leading zeros.
Examples
0)
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwx"" "9990009990000090" Returns: "AFGJKLMQUVWYbcdefghinopqrstwx"
1)
"ABCD" "15" Returns: "A"
2)
"ABCD" "14" Returns: "ABCD"
"ABCD" is the last of the 15 subsequences in L.
3)
"ABCDABCDABCDABCD" "999999999999999" Returns: "ACDBABD"
4)
"akjsflakjsrflkaj" "29384923849283492" Returns: "kjslksrfkaj"
5)
"ABCD" "19203410239121" Returns: "ABD"
19203410239121 % 15 = 11.
Submissions are judged against all 61 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GetSubsequence with a public method string getAt(string s, string pos) · 61 test cases · 2 s / 256 MB per case