Round 1
Questions:
Question
A team of developers at Amazon is working on a feature that checks the strength of a password as it is set by a user. Analysts found that people use their personal information in passwords, which is insecure. The feature searches for the presence of a reference string as a subsequence of any permutation of the password. If any permutation contains the reference string as a subsequence, then the feature determines the minimum cost to remove characters from password so that no permutation contains the string reference as a subsequence. The removal of any character has a cost given in an array, cost, with 26 elements that represent the cost to replace 'a' (cost[0]) through 'Z' (cost[25]). Given two strings password and reference, determine the minimum total cost to remove characters from password so that no permutation contains the string reference as a subsequence.
Note:
- A permutation is a sequence of integers from 1 to n of length n containing each number exactly once, for example [1, 3, 2] is a permutation while [1, 2, 1] is not.
- A subsequence is a sequence that can be derived from another sequence by deleting some or no elements, without changing the order of the remaining elements. For example, given the string "abcde", the following are subsequences: "a", "ace", "be", "bde" etc. while sequences like "dea", "acbde" are not subsequences.
Example Suppose password = "adefgh", reference = "hf", and cost = [1, 0, 0, 2, 4, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. Some possible removals from password so that no permutation contains the string reference as a subsequence are:
- In Case 1 we are removing only a single letter 'h' so the cost of removal in this case becomes 1.
- Similarly in Case 2 we are removing only a single letter 'f' so the cost of removal in this case becomes 4.
Since removing either h or f will remove the existence of reference as a subsequence so we optimally choose to remove 'h' (Case 1), therefore the minimum cost is 1.
Function Description Complete the function minCost in the editor below.
minCost has the following parameters:
- string password: the password string
- string reference: the string which should not exist as a subsequence in any permutation of password
- int cost[26]: the costs to remove each character in the lowercase English alphabet
Returns long int: the minimum cost to remove characters from password such that no permutation contains the reference string as a subsequence
Constraints
- 1 ≤ |password| ≤ 10^5
- 1 ≤ |reference| ≤ 10^5
- 0 ≤ cost[i] ≤ 10^9 for i in range [0, 25]
- The strings password and reference consist of lowercase English letters only.
Sample:
Sample Output: 3
Explanation: An optimal move is to remove the occurrences of the letter 'c' resulting in a modified password = "abdbb". The total cost of removal is = 1*3 = 3.
Question
Developers at Amazon are working on a text generation utility for one of their new products. Currently, the utility generates only special strings. A string is special if there are no matching adjacent characters. Given a string s of length n, generate a special string of length n that is lexicographically greater than s. If multiple such special strings are possible, then return the lexicographically smallest string among them.
Notes:
- Special String: A string is special if there are no two adjacent characters that are the same.
- Lexicographical Order: This is a generalization of the way words are alphabetically ordered in dictionaries. For example, "abc" is lexicographically smaller than "abd" because 'c' comes before 'd' in the alphabet. A string a is lexicographically smaller than a string b if and only if one of the following holds:
- a is a prefix of b, but a is not equal to b. For example, "abc" is smaller than "abcd".
- In the first position where a and b differ, the character in a comes before the character in b in the alphabet. For example, "abc" is smaller than "abd" because 'c' comes before 'd'.
Important Considerations:
- If the character is 'Z', it is the last character in the alphabet and cannot be increased further. The string should not wrap around to 'a' after 'Z'.
- The output string must not have any adjacent characters that are the same.
Example Suppose s = "abbd". Some of the special strings that are lexicographically greater than s are shown.
The lexicographically smallest special string that is greater than "abbd" is "abca".
Function Description Complete the function getSpecialString in the editor below. getSpecialString has the following parameter:
- s: the input string
Returns string: the lexicographically smallest string that is greater than s. If no such special string exists, return "-1".
Constraints:
- 1 ≤ |s| ≤ 10^6
- s consists of lowercase English letters only.
Sample Sample Input For Custom Testing
STDIN FUNCTION abccde → s = "abccde"
Sample Output: abcdab
Explanation Some of the special strings that are lexicographically greater than s are "abcdde", "abcdab", "abcdbc".