Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Substring Start End Same

Last Updated on March 31, 2022 by Ria Pathak

Recursion

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a string `S`, print the `count` of all contiguous substrings that start and end at the same character.

#### For Example:

``````Input : S = "abca"

Resultant Strings : { "a", "b", "c", "a", "abca" }

Output : 5``````

### OBSERVATION:

Every single character starts and ends at the same character, so count of every character will be included in the final count.
See original problem statement here

Can we use `Recursion` here ?

Yes, the problem can be divided into sub problems, for example S = "abca"
find all combinations starting with ‘a’ then move ahead and find all combinations starting with ‘b’. Similarly entire string can be reduced.

### SOLVING APPROACH:

1. Initialize `start` and `end` with `0`.
2. Start by checking, if a character at `start` index matches with character at `end` index (Obviously it will)
3. If Yes, increment by `1` and recursively check for `start` and `end + 1`.
4. If No, recursively check for `start` and `end + 1`.
5. This will be checked till `end` and `start` reaches the end of the string.

### ALGORITHM:

``````i = 0
j = 0
count = 0

if (j reaches at the end of string)
increment i by 1
j = i (start j again from i)

if(j still reaches at the end of string)
return 0  (both i and j reached end)

if(char at i index = char at j index)
increment count by 1 and solve for (i, j + 1)
else
solve for (i, j + 1)``````

### ILLUSTRATION:

``````S = "abca"

i = 0
j = 0
count = 0
Since S[i] = S[j] ('a' = 'a')
count++ => count = 1
j++ => j= 1

i = 0
j = 1
Since S[i] != S[j] ('a' != 'b')
j++ => j = 2

i = 0
j = 2
Since S[i] != S[j] ('a' != 'c')
j++ => j = 3

i = 0
j = 3
Since S[i] = S[j] ('a' = 'a')
count++ => count = 2
j++ => j = 4
j reached at end so reset it
i++ => i = 1
j = i => j = 1

i = 1
j = 1
Since S[i] = S[j] ('b' = 'b')
count++ => count = 3
j++ => j = 2

i = 1
j = 2
Since S[i] != S[j] ('b' != 'c')
j++ => j = 3

i = 1
j = 3
Since S[i] != S[j] ('b' != 'a')
j++ => j = 4
j reached at end so reset it
i++ => i = 2
j = i => j = 2

i = 2
j = 2
Since S[i] = S[j] ('c' = 'c')
count++ => count = 4
j++ => j = 3

i = 2
j = 3
Since S[i] != S[j] ('c' != 'a')
j++ => j = 4
j reached at end so reset it
i++ => i = 3
j = i => j = 3

i = 3
j = 3
Since S[i] = S[i] ('a' = 'a')
count++ => count = 5
j++ => j = 4
j reached at end so reset it
i++ => i = 4
j = i => j = 4
j is still at end so terminate and return count

Resultant count is 5``````

### SOLUTIONS:

```#include <stdio.h>

int substringSES(char *s,int start,int end){
/* when end reaches at the end of the string
still recur for some more cases if present */
if(end == strlen(s)){
start++;
end = start;
}
/* when end reaches at the end of the string
and all cases are covered */
if(end == strlen(s))
return 0;

/* if a char at start index matches char at end index
count it and recur for more cases */
if(s[start] == s[end])
return 1 + substringSES(s, start, end + 1);
else
/* if char at both index does'nt matches skip it
and recur for more cases */
return substringSES(s, start, end + 1);
}

int main()
{
int t;  scanf("%d",&t);
while(t--){
char s[11]; scanf("%s",s);
int start = 0;
int end = strlen(s)-1;
printf("%d\n",substringSES(s,start,start));
}
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

int substringSES(string s,int start,int end){
/* when end reaches at the end of the string
still recur for some more cases if present */
if(end == s.size()){
start++;
end = start;
}
/* when end reaches at the end of the string
and all cases are covered */
if(end == s.size())
return 0;

/* if a char at start index matches char at end index
count it and recur for more cases */
if(s[start] == s[end])
return 1 + substringSES(s, start, end + 1);
else
/* if char at both index does'nt matches skip it
and recur for more cases */
return substringSES(s, start, end + 1);
}

int main()
{
int t;cin>>t;
while(t--){
string s;cin>>s;
int start = 0;
int end = s.size()-1;
cout<<substringSES(s,start,start)<<"\n";
}

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static int substringSES(String s,int start,int end) {
/* when end reaches at the end of the string
still recur for some more cases if present */
if(end == s.length()){
start++;
end = start;
}
/* when end reaches at the end of the string
and all cases are covered */
if(end == s.length())
return 0;

/* if a char at start index matches char at end index
count it and recur for more cases */
if(s.charAt(start) == s.charAt(end))
return 1 + substringSES(s, start, end + 1);
else
/* if char at both index does'nt matches skip it
and recur for more cases */
return substringSES(s, start, end + 1);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
String s = sc.next();
int start = 0;
int end = s.length()-1;
System.out.println(substringSES(s,start,start));
t--;
}
}
}
```
```def substringSES( s, start, end):

if(end == len(s)):
start += 1
end = start

if(end == len(s)):
return 0

if(s[start] == s[end]):
return 1 + substringSES(s, start, end + 1)

else:
return substringSES(s, start, end + 1);

for _ in range(int(input())):

s = input()
start, end = 0, len(s) - 1

print(substringSES(s, start, start))
```

[forminator_quiz id="1034"]

This article tried to discuss the concept of Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.