Longest Special Subsequences You are given a binary string S that contains only 0 and 1....

Transcribed Image Text:

Longest Special Subsequences You are given a binary string S that contains only 0 and 1. Your task is to find the length of the longest special subsequence in string S. A special sequence is a binary sequence that is in the form of 0*1*0*1*, where 0* represents an empty or a consecutive sequence of 0's and 1* represents an empty or a consecutive sequence of 1's (same as in the Regular Expression). For example, 001, 0110, 1, 0, and 0110011 are the examples of special sequence, whereas 01010 and 1010 are not. Note: A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. Input format • First line: T (number of test cases) . For each test case: o First line: N (length of the string S) o Second line: String S Output format For each test case, print the length of the longest special subsequence in S. Constraints 1≤T≤ 105 Constraints 1≤T≤ 105 1 ≤N ≤ 105 S contains only 0 and 1 Sum of N over all test cases < 106 Sample Input % 2 4 0101 8 10101010 Explanation Sample Output 4 5 % Explanation In second test case, one of the longest special subsequence is 01101, whose length is 5. Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code. will be run on multiple test cases. Therefore, your code must solve this problem statement. Longest Special Subsequences You are given a binary string S that contains only 0 and 1. Your task is to find the length of the longest special subsequence in string S. A special sequence is a binary sequence that is in the form of 0*1*0*1*, where 0* represents an empty or a consecutive sequence of 0's and 1* represents an empty or a consecutive sequence of 1's (same as in the Regular Expression). For example, 001, 0110, 1, 0, and 0110011 are the examples of special sequence, whereas 01010 and 1010 are not. Note: A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. Input format • First line: T (number of test cases) . For each test case: o First line: N (length of the string S) o Second line: String S Output format For each test case, print the length of the longest special subsequence in S. Constraints 1≤T≤ 105 Constraints 1≤T≤ 105 1 ≤N ≤ 105 S contains only 0 and 1 Sum of N over all test cases < 106 Sample Input % 2 4 0101 8 10101010 Explanation Sample Output 4 5 % Explanation In second test case, one of the longest special subsequence is 01101, whose length is 5. Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code. will be run on multiple test cases. Therefore, your code must solve this problem statement.

Answer rating: 100% (QA)

Heres the Python code to implement this approach Function to find the length of the longest special ... View the full answer