Lighthouse Flag Broadcast - Google 18th July Online Assessment

Problem Preview

"Every evening, the keeper of the Saltmere lighthouse raises a sequence of signal flags along the harbour mast. Each flag contains one lowercase letter, and the flags remain in the order in which they were raised. The glow strength of a flag is determined by its letter. The letter a has strength 1, b has strength 2, and so on up to z, which has strength 26. The harbour authority requires the keeper to select exactly k flags from the sequence without changing their original order. The total glow strength of the selected flags must be at least f. Among all selections that satisfy these conditions, determine the lexicographically smallest string formed by the selected flags. Function Description Implement the function minFlagBroadcastCode. Parameters n: The number of flags in the sequence. s: A string of n lowercase English letters representing the flags in their original order. k: The exact number of flags that must be selected. f: The minimum total glow strength required from the selected flags. Returns The lexicographically smallest string of length k that can be obtained by deleting n minus k characters from s while preserving the order of the remaining characters and ensuring that their total glow strength is at least f. Input Format The first line contains a single integer n, the number of flags. The second line contains the string s of exactly n lowercase English letters. The third line contains a single integer k, the number of flags that must be selected. The fourth line contains a single integer f, the minimum required glow strength. Output Format Print a single line containing the lexicographically smallest valid broadcast string. Example Input: Plaintext 5 dcbac 3 7 Output cac Explanation: The flags, in hoisted order, are d(4) c(3) b(2) a(1) c(3), where the number in parentheses is the glow strength. We must keep exactly 3 flags whose strengths sum to at least 7, and among all such choices we want the reading that sorts earliest alphabetically. Keeping the very first flag 'd' would force the reading to start with 'd', but 'd' is alphabetically later than 'c', so any reading starting with a kept 'c' beats it — as long as a valid completion exists. Dropping the first flag 'd' and starting from the flag 'c' at position 2 is safe here: the remaining flags from position 2 onward are c(3) b(2) a(1) c(3) whose three largest strengths (3, 3, 2) already sum to at least 7."