Substring Start End Same

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:

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 MYCODE | Competitive Programming.