Substring - Can someone check which case my code is missing?

help
1

I was solving one problem in the contest which has now ended can someone tell why it is giving wrong answer .
The question link Is- CodeChef: Practical coding for everyone
My solution link is - CodeChef: Practical coding for everyone
I know the question is a easy one but i am not able to get the algorithm in my mind which is shorter than this .

subString(s, n):
for i in range(n):
    for len in range(i + 1, n + 1):
        tempst=s[i: len]
        count=tempst.count(X)
        if(count==Y):
            lst.append(s[i: len])

S=input()
X=input()
Y=int(input())
lst=[]
temp = S.count(X)
if(X not in S):
    print(0)
else:
    subString(S, len(S))
    print(len(lst))
1 Like
2

Can anyone help ?

3

Do you want to know real solution or error in your solution , I think even if you correct your code it is O(N^3) , I might be wrong as I don’t know much python.

1 Like
5

How o/p will be 5?

1 Like
7

1 → divide the string at each point where character x appears.
i.e. for string “abcdefgcdefghjkgkgg” for char - g and y = 2
string abcdef g cdef g hjk g k g g
2 → store number of characters+1 for each division
i.e. count[] = 7 g 5 g 4 g 2 g 1 g 1 (g should not be stored in array, it is given only for division)
3 → for every i upto i+y<n add count[i]*count[i+y] in the result.

Time complexity : O(n)

ravan a 2
r a v a n
count[] = 2 2 2
res = count[0]*count[2] // + (count[1]*count[3] + count[2]*count[4] …)

void solution(){
string s;
char x;
int y, p = 1, n;
ll ans = 0;
cin >> s >> x >> y;
n = s.size();
vector<int> v;
for(int i=0; i<n; i++){
	if(s[i]==x){
		v.push_back(p);
		p = 1;
	}else{
		p++;
	}
}
if(s[n-1]==x) v.push_back(1);
else v.push_back(p);
for(int i=0; i+y < v.size(); i++){
	ans += v[i]*v[i+y];
}
cout << ans << '\n';

}

1 Like
8

I thank everyone for the replies and guidance and letting me know the solution is not optimized which i knew a little earlier .
Thanks to adyand for sharing the logic .