After learning basics of arrays and strings, Dark started wondering that if we can sort…
- User
After learning basics of arrays and strings, Dark started wondering that if we can sort the numbers then why not STRINGS?
Deeply thinking and looking the various strings lying in the string pool, he decided to ascend or descend the string according to his wish.
Ascending means strings having all the characters in a string in a order like A,B,C,D,...,Z while descending means string having all characters in a reverse order that is first all Z,Y,X,...,A and so on....
Note: String may contain all the characters available on the normal keyboard. Thus Dark want you to help him design a code to sort the strings according to his wish the code has to sort either ascending or descending...
To make it easy, Dark wants to print only the characters which are Upper Case Alphabets present in the string in sorted form and don't display the other characters of the string.
Note: String will be only one word with mixture of any key present in the normal keyboard. Input:
The first line contains T, the number of test cases. Followed by T lines each contains space separated a single string 'S' and a number 'N'.
N is even--> Ascending
N is odd--> Descending
Output:
For every test case print the sorted form of the string. Print "NULL" if their is no UPPER CASE ALPHABETS present in the string.
Constraints:
1 ≤ T ≤ 500 1 ≤ |S| ≤ 100000 0 ≤ N ≤ 100
Author : Darshak Mehta
SAMPLE INPUT 4 AABAHD 0 AABGHAD 1 AXBCD 0 AXBCD 1
SAMPLE OUTPUT AAABDH HGDBAAA ABCDX XDCBA
Assistant
We need to interpret the problem. It says: "After learning basics of arrays and strings, Dark started wondering that if we can sort the numbers then why not STRINGS? Deeply thinking and looking the various strings lying in the string pool, he decided to ascend or descend the string according to his wish. Ascending means strings having all the characters in a string in a order like A,B,C,D,...,Z while descending means string having all characters in a reverse order that is first all Z,Y,X,...,A and so on.... Note: String may contain all the characters available on the normal keyboard. Thus Dark want you to help him design a code to sort the strings according to his wish the code has to sort either ascending or descending... To make it easy, Dark wants to print only the characters which are Upper Case Alphabets present in the string in sorted form and don't display the other characters of the string. Note: String will be only one word with mixture of any key present in the normal keyboard. Input: The first line contains T, the number of test cases. Followed by T lines each contains space separated a single string 'S' and a number 'N'. N is even--> Ascending N is odd--> Descending Output: For every test case print the sorted form of the string. Print "NULL" if their is no UPPER CASE ALPHABETS present in the string."
Given sample: Input: 4 AABAHD 0 AABGHAD 1 AXBCD 0 AXBCD 1
Output: AAABDH HGDBAAA ABCDX XDCBA
Let's verify: First: S = "AABAHD", N=0 (even, ascending). Only uppercase alphabets? It's all uppercase: A, A, B, A, H, D. So filter only uppercase? Already all uppercase. Then sort ascending: alphabetical: A, A, A, B, D, H => AAABDH. Output is AAABDH. Good.
Second: S = "AABGHAD", N=1 (odd, descending). Uppercase: A A B G H A D. Sort descending: Z...A, but only the letters present, so descending order: H G D B A A A? Actually highest letter: H, then G, then D, then B, then A's. So H G D B A A A => H G D B A A A. But the sample output is "HGDBAAA". Yes exactly.
Third: "AXBCD" N=0 ascending => sorted ascending: A B C D X => "ABCDX"? Wait ascending order: A, B, C, D, X => ABCDX. Output: ABCDX. Good.
Fourth: "AXBCD" N=1 descending => X D C B A => "XDCBA". Output: XDCBA. Good.
So essentially we need to: For each test case, extract uppercase letters (A-Z) from the input string, then sort them in ascending (A to Z) if N is even, or descending (Z to A) if N is odd, then output the sorted string. If no uppercase letters, output "NULL".
Constraints: T up to 500, |S| up to 100k. So total input length can be large (500*100k = 50 million). We need efficient processing. Counting sort (frequency count) would be suitable since only 26 letters. We can count occurrences of each uppercase letter in the string (using an array of size 26). Then generate sorted output: if ascending, iterate from 'A' to 'Z' and add each letter times its count. If descending, iterate from 'Z' to 'A'. Then output.
Edge cases: The string may contain any characters: uppercase, lowercase, digits, punctuation. Only uppercase letters count.
Note: N is a number, could be 0 to 100. Even/odd determine direction. So we don't need to sort other characters.
Implementation: Read T. For each test case, read S and N. The line format: "AABAHD 0". So we can read as string and integer. S can be up to 100k length, may contain spaces? "String will be only one word with mixture of any key present in the normal keyboard." So the string doesn't contain spaces; it's a single token. So we can read token and integer.
Important: Input size large. Use fast I/O in C++ (ios_base::sync_with_stdio(false); cin.tie(NULL);). Or use scanf/printf.
In Python, careful with input speed for large strings. Use sys.stdin.read() or sys.stdin.buffer. Since total length up to 50 million, Python might be okay if we read line by line and process with count array, but 50M char reading might be heavy but still feasible if done efficiently (using sys.stdin.buffer). But we need to output maybe large strings as well (total output could be up to 50M). In Python, we can use sys.stdout.write. Use collections.Counter or manual count.
Better approach: For each test case, iterate over characters of S, check if 'A' <= c <= 'Z', increment count[ord(c)-65]. Then after count, if sum(count)==0, output "NULL". else, generate output string. For ascending: ''.join([chr(i+65) * count[i] for i in range(26)]) ; for descending: range(25,-1,-1). This could be memory heavy if the string is long (100k) but output string length is up to the number of uppercase letters, which is up to 100k, which is okay. In Python, building a string of length 100k is fine; but for T=500, total output could be 50M, building that as one big string might be memory heavy but we output per test case. So we can output directly.
But careful: In Python, using multiplication to create repeated characters might create large strings; it's okay.
Alternative: For each test case, we can compute counts and then if descending, iterate from Z to A and write to stdout the char repeated count times, using sys.stdout.write(chr(i+65) * count[i]) for each, then newline.
We need to be careful about reading lines: The input might have trailing spaces; but we can use split. However, the string S may contain spaces? It says one word, so no spaces. So split works.
But if S is huge (100k), splitting the line into parts using split() will create a list of strings, one being S and the other N. That's okay because the line length is about 100k+ some digits. So we can read line, then split. However, reading line with newline: We could use sys.stdin.readline().split(). That yields two tokens: first is S, second is N as string. Then N = int(...). Good.
But need to handle that the string might contain other characters that are not letters. The counting only for uppercase.
Potential pitfalls: The problem statement says: "String will be only one word with mixture of any key present in the normal keyboard." So it's a single token.
Implementation Plan (Python):
import sys
def solve(): data = sys.stdin.buffer.read().split() # But careful: reading all input at once might consume a lot of memory (up to 50M + overhead). That's okay? 50M bytes maybe okay in modern machines (about 50 MB). But could be borderline but fine. Alternatively read line by line. # Let's use line-by-line to be safe: for _ in range(T) # First read T from first line. # But we can use sys.stdin.buffer.readline.
Better: Use sys.stdin.buffer to read lines.
Pseudo-code:
import sys
def main(): input = sys.stdin.buffer.readline T_line = input() if not T_line: return T = int(T_line) out_lines = [] for _ in range(T): line = input().decode().strip()? Actually read as bytes, can decode later but we can split as bytes and then decode only the string? We'll treat bytes: line = input().split() => list of bytes. Then S_bytes = line[0], N = int(line[1]). But S_bytes is bytes; we need to process each character. We could convert to string via .decode() but that might allocate a new string; we can process bytes and check if byte between 65 and 90 inclusive (A-Z). That may be faster. So we can keep as bytes.
So:
line = input().split() if not line: break? maybe not.
S = line[0] # bytes object N = int(line[1])
count = [0]*26 for b in S: if 65 <= b <= 90: # A-Z count[b-65] += 1
if sum(count) == 0: out_lines.append("NULL") else: if N % 2 == 0: # even -> ascending # construct string # Using list comprehension then join # Or we can build string by writing to buffer # We'll use a list of parts to join. parts = [] for i in range(26): if count[i]: parts.append(chr(i+65) * count[i]) out_lines.append(''.join(parts)) else: # odd -> descending parts = [] for i in range(25, -1, -1): if count[i]: parts.append(chr(i+65) * count[i]) out_lines.append(''.join(parts))
After loop, sys.stdout.write('\n'.join(out_lines))
But careful: Input size large; building 'parts' for each test case with many repeated characters: For each i, chr(i+65) * count[i] creates a string of length count[i]. Then join concatenates. That's fine.
Potential memory: out_lines collects all outputs; if total output huge, could be memory heavy. Better to write directly to stdout line by line: use sys.stdout.write for each test case. But then we need to manage newline. We can use sys.stdout.write after each test case. However, sys.stdout.write might be slower if called many times? But we can buffer ourselves. But simple approach: use list and then join at the end; if total output up to 50M, that is 50MB plus overhead, maybe acceptable. But to be safe, we can write per test case.
I'll do per test case writing to sys.stdout.buffer:
out = sys.stdout.buffer for each test: if sum(count)==0: out.write(b"NULL\n") else: if N%2==0: for i in range(26): if count[i]: out.write((chr(i+65)*count[i]).encode()) # but that creates string then encode; perhaps we can write bytes. Better: we can write repeated bytes directly: out.write(bytes([i+65]) * count[i])? Actually bytes([i+65]) creates a one-byte bytes object; multiply replicates that many times. That's efficient. Eg: out.write(bytes([i+65]) * count[i]). That writes as bytes without decoding. Then after loop, write newline.
So we can use bytes output: out.write(b'...') for NULL else:
if N%2==0: for i in range(26): if count[i]: out.write(bytes([i+65]) * count[i]) else: for i in range(25, -1, -1): if count[i]: out.write(bytes([i+65]) * count[i]) out.write(b'\n')
That avoids constructing huge string. Good.
Now reading: We'll read as bytes line, split, get S_bytes.
Implementation details:
import sys
def main(): data_in = sys.stdin.buffer out = sys.stdout.buffer first = data_in.readline() if not first: return T = int(first) for _ in range(T): line = data_in.readline() # Possibly blank lines? Not expected. parts = line.split() # If there might be extra spaces? Use maxsplit=1? Not needed. S_bytes = parts[0] N = int(parts[1]) count = [0]*26 for b in S_bytes: if 65 <= b <= 90: count[b-65] += 1 total = 0 for c in count: total += c if total == 0: out.write(b'NULL\n') else: if N % 2 == 0: # even, ascending for i in range(26): cnt = count[i] if cnt: out.write(bytes([i+65]) * cnt) else: for i in range(25, -1, -1): cnt = count[i] if cnt: out.write(bytes([i+65]) * cnt) out.write(b'\n')
if name == "main": main()
Check sample:
Input: 4 AABAHD 0 AABGHAD 1 AXBCD 0 AXBCD 1
Our code: For each S_bytes, counts. Outputs: For first: A:3? Actually A appears 3? AABAHD: A,A,B,A,H,D -> A:3, B:1, H:1, D:1. Ascending: A A A B D H? Wait D comes before H? Actually ascending: A B D H? Let's order: A (65), B (66), D (68), H (72). So output: AAA B D H => AAABDH. Good.
But we need to ensure ordering: In ascending, we output from i=0 (A) to 25 (Z). So A's, then B, then ... So indeed A's, then B, then C (none), then D, then ... H. So string: AAA B D H = AAABDH. That matches.
Second: descending: i=25 to 0. H is 71? Actually H is ascii 72, so index 7? A=65 index0, B=1, C=2, D=3, E=4, F=5, G=6, H=7. So descending: H, G, D, B, A. Output: H G D B A A A => HGDBAAA. Good.
Third: ascending: A B C D X => ABCDX. X is index 23, so after D it outputs ... until X, so ABCDX. Good.
Fourth: descending: X D C B A => XDCBA. Good.
Edge: If uppercase letters only, but there are lowercase letters? They are ignored.
Test: "abc123!@#" 0 -> no uppercase -> NULL.
Now performance: For each test case, we iterate over S_bytes once, O(|S|). Counting array constant. Output generation: we iterate over 26 and write bytes repeated. That is fine.
Memory: We only store count array per test case.
Thus solution is efficient.
Now check constraints: T up to 500, each |S| up to 100k, so total O(total length) = 50M, which is fine in Python if optimized. Using bytes and writing directly should be fast.
Potential pitfall: In reading lines, the string S might contain spaces? Problem says "String will be only one word", so no spaces. So split works. However, if S could contain spaces, then split would break it into multiple tokens. But problem says only one word, so safe.
But what if there are trailing spaces? .split() will trim them.
Also, maybe there could be multiple spaces? But .split() without arguments splits on any whitespace. So reading line and split yields tokens. The first token is S, second token is N. That works.
We should consider if the line could have more than two tokens? Probably not.
One more nuance: The number N is given as integer, could be 0, even. N can be up to 100.
Now, what about uppercase letters? Only English uppercase? Yes, A-Z.
Thus solution done.
We should present explanation in the answer: Use frequency counting because only 26 possible letters. For each test case, count uppercase letters. If no uppercase, output NULL. Else, if N even, output letters from A to Z each repeated count times; if N odd, from Z to A.
Now I'll produce the final answer. ```python
import sys
def solve() -> None: data_in = sys.stdin.buffer out = sys.stdout.buffer
t_line = data_in.readline() if not t_line: return T = int(t_line) for _ in range(T): line = data_in.readline() # each line contains the string and the number N separated by a space parts = line.split() # parts[0] is the string as a bytes object, parts[1] is N as bytes s_bytes = parts[0] N = int(parts[1]) # frequency of uppercase letters (A-Z) cnt = [0] * 26 for b in s_bytes: # ASCII range of 'A' to 'Z' is 65..90 if 65 <= b <= 90: cnt[b - 65] += 1 total_upper = sum(cnt) if total_upper == 0: out.write(b'NULL\n') continue if N % 2 == 0: # even → ascending (A..Z) for i in range(26): c = cnt[i] if c: out.write(bytes([i + 65]) * c) else: # odd → descending (Z..A) for i in range(25, -1, -1): c = cnt[i] if c: out.write(bytes([i + 65]) * c) out.write(b'\n')if name == "main": solve()