Substring Start End Same

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.

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

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 .