Some terrorist attacks on Indian border. Now Indian Army have to send his soldiers to…
- User
Some terrorist attacks on Indian border. Now Indian Army have to send his soldiers to fight against terrorist. There are total N soldiers in the camp. Every soldier has a skill denoted by a single character lies between A-Z (all skills are in CAPITAL LETTERS). Now commander gave order to stand all the soldiers in a row, so that he can select a segment of maximum number of soldiers from the row to sent them for fighting against the terrorist. INPUT
First line contains number of test cases T, for each test case a single line represents soldiers standing in a row with their skill.
OUTPUT
A single line representing maximum number of soldiers that commander selects for each test case.
Constraints:
1 ≤ T ≤100
1 ≤ N ≤ 10000
SAMPLE INPUT 2 ABDEFGABEF GHJKLMNOPQ
SAMPLE OUTPUT 6 10
Explanation
For first test case, the soldier skills are “ABDEFGABEF” maximum soldiers with different skills are “ABDEFG” and “BDEFGA”, "DEFGAB" with length 6.
Assistant
We have a problem description: "Some terrorist attacks on Indian border. Now Indian Army have to send his soldiers to fight against terrorist. There are total N soldiers in the camp. Every soldier has a skill denoted by a single character lies between A-Z (all skills are CAPITAL LETTERS). Now commander gave order to stand all the soldiers in a row, so that he can select a segment of maximum number of soldiers from the row to sent them for fighting against the terrorist." The input: T test cases, each line a string representing soldiers' skills. Output: maximum number of soldiers that commander selects for each test case.
From sample: "ABDEFGABEF" -> 6. And "GHJKLMNOPQ" -> 10. Clearly it's the classic problem: longest substring with distinct characters (no repeated characters). Indeed, "ABDEFGABEF" has longest substring of distinct characters as "ABDEFG" length 6 (others also length 6). And "GHJKLMNOPQ" all distinct so length = 10.
Constraints: T ≤ 100, N ≤ 10000. So we need to compute for each string the length of longest substring without repeating characters. Standard sliding window approach O(N) per string. With N up to 10^4, it's fine.
Implementation: For each test case, read string s. Maintain a window [start, i) with i scanning. Use a dictionary (or array of size 26) to count characters in window. For each i, add s[i], while count[s[i]] > 1, move start forward and decrement count[s[start]]. Keep track of max length.
Alternatively, we can use last occurrence map to jump start.
Given that characters are A-Z, we can use array of size 26.
Thus solution straightforward.
Edge cases: empty string? N >=1, so not empty. Characters only uppercase A-Z, so 26.
Multiple test cases T up to 100.
Hence we output max length each on its own line.
Let's double-check sample: For "ABDEFGABEF", distinct substring max length = 6. Good. For "GHJKLMNOPQ", length = 10. Yes.
Thus answer: print for each test case the integer.
We need to write code accordingly.
But note: The problem statement says "maximum number of soldiers that commander selects" - we need longest segment with all distinct skills? Possibly they mean "select a segment of maximum number of soldiers" such that each soldier's skill is unique within the segment. That's what sample suggests.
Check: Could there be any twist? The description: "Now commander gave order to stand all the soldiers in a row, so that he can select a segment of maximum number of soldiers from the row to sent them for fighting against the terrorist." Usually such problems: find longest contiguous subarray with all distinct characters. So yes.
Thus we implement.
Pseudo:
def longest_unique_substring(s): n = len(s) if n == 0: return 0 start = 0 max_len = 0 last_index = [-1]*26 for i in range(n): idx = ord(s[i]) - ord('A') if last_index[idx] >= start: start = last_index[idx] + 1 last_index[idx] = i max_len = max(max_len, i - start + 1) return max_len
or sliding window with counts.
Time O(N) per case.
Implementation details: read input. There are T test cases. Each test case line may contain spaces? No, it's a single string of uppercase letters. So we can read using input().strip().
Edge cases: Input might have leading/trailing whitespace; trim.
Now provide solution in Python (likely allowed). We'll produce final answer.
But before final, we need to ensure we understand problem correctly: Could it be something else? Like maximum number of soldiers with distinct skills? But then "segment" implies contiguous. So distinct substring.
Check constraints: N <= 10000, not huge, so O(N) fine.
Thus final answer: Implement solution.
One more thought: The problem statement says "select a segment of maximum number of soldiers from the row to sent them for fighting against the terrorist." It doesn't explicitly say that the skills must be different; however, typical coding problem is "longest substring without repeating characters". The sample indicates distinct. Also if you could select any segment, the max would be all soldiers, but sample 1 gave 6 not 10, so distinctness required. So correct.
Thus output each max length.
Now produce solution explanation and code.
We'll write:
import sys
def longest_distinct(s): last_seen = [-1]*26 start = 0 max_len = 0 for i,ch in enumerate(s): idx = ord(ch)-65 if last_seen[idx] >= start: start = last_seen[idx] + 1 last_seen[idx] = i cur_len = i - start + 1 if cur_len > max_len: max_len = cur_len return max_len
def main(): data = sys.stdin.read().splitlines() t = int(data[0].strip()) out_lines = [] for i in range(1, t+1): s = data[i].strip() out_lines.append(str(longest_distinct(s))) sys.stdout.write("\n".join(out_lines))
if name == "main": main()
This handles reading lines.
Alternatively, use input() loop.
Ensure that if T lines maybe less? But safe.
Edge: There could be extra blank lines? But not likely.
So final answer. ```python
import sys
def longest_distinct_substring(s: str) -> int: """ Returns the length of the longest substring with all distinct characters. Characters are guaranteed to be uppercase English letters 'A'-'Z'. """ # last occurrence index of each character; -1 means not seen yet last_seen = [-1] * 26 start = 0 # start index of current window max_len = 0
for i, ch in enumerate(s): idx = ord(ch) - ord('A') # map 'A'..'Z' to 0..25 # if this character already appears inside the current window if last_seen[idx] >= start: start = last_seen[idx] + 1 # shrink window from the left last_seen[idx] = i # update last occurrence cur_len = i - start + 1 if cur_len > max_len: max_len = cur_len return max_lendef main() -> None: data = sys.stdin.read().splitlines() if not data: return t = int(data[0].strip()) out_lines = [] for i in range(1, t + 1): s = data[i].strip() out_lines.append(str(longest_distinct_substring(s))) sys.stdout.write("\n".join(out_lines))
if name == "main": main()