need correction in my approach
Shlok and Sachin are good friends. Shlok wanted to test Sachin, so he wrote down a string S with length N and one character X. He wants Sachin to find the number of different substrings of S which contain the character X at least once. Sachin is busy with his girlfriend, so he needs you to find the answer.
Two substrings of S are considered different if their positions in S are different.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains a string S with length N, followed by a space and a character X.
Output
For each test case, print a single line containing one integer — the number of substrings of S that contain X.
Constraints
1≤T≤1,000
1≤N≤106
S contains only lowercase English letters
X is a lowercase English letter
the sum of N over all test cases does not exceed 106
Subtasks
Subtask #1 (30 points): the sum of N over all test cases does not exceed 103
Subtask #2 (70 points): original constraints
Example Input
2
3
abb b
6
abcabc c
Example Output
5
15
Explanation
Example case 1: The string "abb" has six substrings: "a", "b", "b", "ab", "bb", "abb". The substrings that contain 'b' are "b", "b", "ab", "bb", "abb".
Two substrings of S are considered different if their positions in S are different.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains a string S with length N, followed by a space and a character X.
Output
For each test case, print a single line containing one integer — the number of substrings of S that contain X.
Constraints
1≤T≤1,000
1≤N≤106
S contains only lowercase English letters
X is a lowercase English letter
the sum of N over all test cases does not exceed 106
Subtasks
Subtask #1 (30 points): the sum of N over all test cases does not exceed 103
Subtask #2 (70 points): original constraints
Example Input
2
3
abb b
6
abcabc c
Example Output
5
15
Explanation
Example case 1: The string "abb" has six substrings: "a", "b", "b", "ab", "bb", "abb". The substrings that contain 'b' are "b", "b", "ab", "bb", "abb".
Last edited on
Perhaps this is easier to read, being better formatted:
https://www.codechef.com/APRIL19B/problems/STRCH
https://www.codechef.com/APRIL19B/problems/STRCH
> Where is the approach failing ?
No idea - we can't see your code.
> My approach:declared a variable res where res=n*(n+1)/2 and I have made a vector ...
Describing what you did, and what you actually did are two different things.
Your approach might actually work if implemented correctly (I don't know), but if you've made a mistake between your design and your implementation, you lose anyway.
> But i am getting correct answer in only few test cases . Where is the approach failing ?
Well the first task for you would be to try and invent more test cases which you "know" the answer to.
For example, two edge cases where the answer is zero and some large number.
2
3
abc d
6
cccccc c
> I have made a vector of all the indices
CF problems are rarely solved by trying every possible combination and then counting.
Mostly, they rely on the mathematical understanding of the problem (in this case permutations and combinations) to arrive at an algorithmic answer to the problem.
No idea - we can't see your code.
> My approach:declared a variable res where res=n*(n+1)/2 and I have made a vector ...
Describing what you did, and what you actually did are two different things.
Your approach might actually work if implemented correctly (I don't know), but if you've made a mistake between your design and your implementation, you lose anyway.
> But i am getting correct answer in only few test cases . Where is the approach failing ?
Well the first task for you would be to try and invent more test cases which you "know" the answer to.
For example, two edge cases where the answer is zero and some large number.
2
3
abc d
6
cccccc c
> I have made a vector of all the indices
CF problems are rarely solved by trying every possible combination and then counting.
Mostly, they rely on the mathematical understanding of the problem (in this case permutations and combinations) to arrive at an algorithmic answer to the problem.
Topic archived. No new replies allowed.