[Solution] Disjoint XOR CodeChef Solution

Problem

Chef has a binary string $S$ of length $N$. Chef wants to find two disjoint substrings of equal length, such that their bitwise XOR is maximised.

Formally, Chef wants to find $L_1, R_1, L_2,$ and $R_2$ such that:

• $1 \le L_1 \le R_1 \lt L_2 \le R_2 \le N$, that is, the substrings are disjoint (have no common elements);
• $|R_1 - L_1 + 1| = |R_2 - L_2 + 1|$, that is, the substrings have equal length;
• $S_{L_1 \dots R_1} \oplus S_{L_2 \dots R_2}$ is maximised, where $\oplus$ is the bitwise XOR operation.

Output the maximum XOR value in decimal notation. Since the value can be large, output it module $10^9+7$.

Note that a substring is formed by deleting some (possibly zero) characters from the beginning and some (possibly zero) characters from the end of the string.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains a single integer $N$ denoting the length of string $S$.
  • The second line of each test case contains a binary string $S$ of length $N$ containing $0$s and $1$s only.

Output Format

For each test case, output the maximum XOR value in decimal notation. Since the value can be large, output it module $10^9+7$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Explanation:

Test case $1$: We can choose $L_1 = 1, R_1 = 2, L_2 = 3,$ and $R_2 = 4$. Thus, the chosen substrings are $10$ and $01$. The XOR of these substrings is $11$ whose decimal equivalent is $3$.

Test case $2$: We can choose $L_1 = 2, R_1 = 2, L_2 = 4,$ and $R_2 = 4$. Thus, the chosen substrings are $1$ and $1$. The XOR of these substrings is $0$ whose decimal equivalent is $0$.

Test case $3$: We can choose $L_1 = 1, R_1 = 1, L_2 = 3,$ and $R_2 = 3$. Thus, the chosen substrings are $0$ and $1$. The XOR of these substrings is $1$ whose decimal equivalent is $1$.