Last Updated on March 31, 2022 by Ria Pathak

### CONCEPTS USED:

Recursion

### DIFFICULTY LEVEL:

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:

- Initialize
`start`

and`end`

with`0`

.- Start by checking, if a character at
`start`

index matches with character at`end`

index (Obviously it will)- If Yes, increment by
`1`

and recursively check for`start`

and`end + 1`

.- If No, recursively check for
`start`

and`end + 1`

.- 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.