Lexicographically Small String - Teradata Online Assessment

Problem Preview

"You are given a string `S` of length `N` consisting of lowercase English letters. Each lowercase letter (`'a'` to `'z'`) belongs to one of two groups: **Black** or **White**. The group assignment is fixed for every letter, meaning all occurrences of the same letter always have the same group. You may perform the following operation any number of times: * Select any two adjacent characters and swap them **only if their corresponding letters belong to different groups**. Determine the lexicographically smallest string that can be obtained after performing any number of valid operations. --- ## Input Format The first line contains an integer `T`, the number of test cases. For each test case: * The first line contains an integer `N`, the length of the string. * The second line contains the string `S`. * The third line contains a string `groups` of length `26`, consisting only of `'B'` and `'W'`. * `groups[0]` represents the group of `'a'`. * `groups[1]` represents the group of `'b'`. * ... * `groups[25]` represents the group of `'z'`. --- ## Output Format For each test case, print the lexicographically smallest string that can be obtained. --- ## Constraints * `1 ≤ T ≤ 5` * `2 ≤ N ≤ 16000` * The sum of `N` over all test cases does not exceed `16000` * `S` contains only lowercase English letters. * `groups` contains exactly `26` characters, each either `'B'` or `'W'`. --- ## Sample Input ```text id="in1" 1 4 ahag BBBBBBBWBBBBBBBBBBBBBBBBBB ``` ## Sample Output ```text id="out1" aagh ``` --- ## Explanation Only the letter `'h'` belongs to the **White** group, while `'a'` and `'g'` belong to the **Black** group. A possible sequence of operations is: * Swap the adjacent characters `'h'` and `'a'` (different groups): `ahag → ahag` * Swap the adjacent characters `'h'` and `'g'` (different groups): `ahag → aagh` No further sequence of valid swaps can produce a lexicographically smaller string. --- ## Expected Approach Observe that adjacent swaps are allowed only between characters belonging to different groups. Characters of the same group cannot cross each other, so their relative order remains fixed. This property can be exploited to construct the lexicographically smallest reachable string efficiently. **Time Complexity:** `O(N log N)` or better. **Space Complexity:** `O(N)`"