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

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

Can anyone help ?

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

How o/p will be 5?

1 Like

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

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 .