Balanced Substring codeforces solution

For Solution

Click Here!

You are given a string ss, consisting of nn letters, each letter is either ‘a‘ or ‘b‘. The letters in the string are numbered from 11 to nn.

s[l;r]s[l;r] is a continuous substring of letters from index ll to rr of the string inclusive.

A string is called balanced if the number of letters ‘a‘ in it is equal to the number of letters ‘b‘. For example, strings “baba” and “aabbab” are balanced and strings “aaab” and “b” are not.

Find any non-empty balanced substring s[l;r]s[l;r] of string ss. Print its ll and rr (1lrn1≤l≤r≤n). If there is no such substring, then print 1−1 1−1.

Balanced Substring solution codeforces

The first line contains a single integer tt (1t10001≤t≤1000) — the number of testcases.

Then the descriptions of tt testcases follow.

The first line of the testcase contains a single integer nn (1n501≤n≤50) — the length of the string.

The second line of the testcase contains a string ss, consisting of nn letters, each letter is either ‘a‘ or ‘b‘.

Balanced Substring solution codeforces

For each testcase print two integers. If there exists a non-empty balanced substring s[l;r]s[l;r], then print ll rr (1lrn1≤l≤r≤n). Otherwise, print 1−1 1−1.

Example

input

Copy
4
1
a
6
abbaba
6
abbaba
9
babbabbaa

output

Copy
-1 -1
1 6
3 6
2 5

Balanced Substring solution codeforces

In the first testcase there are no non-empty balanced subtrings.

In the second and third testcases there are multiple balanced substrings, including the entire string “abbaba” and substring “baba“.

For Solution

Click Here!

Leave a Comment