{"id":1026,"date":"2020-06-10T10:00:57","date_gmt":"2020-06-10T10:00:57","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1026"},"modified":"2022-03-31T11:45:48","modified_gmt":"2022-03-31T11:45:48","slug":"substring-start-end-same","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/substring-start-end-same\/","title":{"rendered":"Substring Start End Same"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a string S<\/code>, print the count<\/code> of all contiguous substrings that start and end at the same character.<\/p>\n<\/blockquote>\n

For Example:<\/h4>\n
Input : S = "abca"\n\nResultant Strings : { "a", "b", "c", "a", "abca" }\n\nOutput : 5<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
Every single character starts and ends at the same character, so count of every character will be included in the final count.
\n<\/strong><\/u><\/a><\/p>\n<\/blockquote>\n
Can we use Recursion<\/code> here ?<\/em><\/strong><\/p>\n
\n
Yes, the problem can be divided into sub problems, for example S = "abca"
\nfind all combinations starting with ‘a’ then move ahead and find all combinations starting with ‘b’. Similarly entire string can be reduced. <\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. Initialize start<\/code> and end<\/code> with 0<\/code>.  <\/li>\n
  2. Start by checking, if a character at start<\/code> index matches with character at end<\/code> index (Obviously it will)<\/li>\n
  3. If Yes, increment by 1<\/code> and recursively check for start<\/code> and end + 1<\/code>.<\/li>\n
  4. If No, recursively check for start<\/code> and end + 1<\/code>.<\/li>\n
  5. This will be checked till end<\/code> and start<\/code> reaches the end of the string.<\/li>\n<\/ol>\n<\/blockquote>\n
    ALGORITHM:<\/h3>\n
    i = 0 \nj = 0 \ncount = 0\n\nif (j reaches at the end of string)\n    increment i by 1\n    j = i (start j again from i)\n\nif(j still reaches at the end of string)\n    return 0  (both i and j reached end)\n\nif(char at i index = char at j index)\n    increment count by 1 and solve for (i, j + 1)\nelse\n    solve for (i, j + 1)<\/code><\/pre>\n
    ILLUSTRATION:<\/h3>\n
    S = "abca"\n\ni = 0\nj = 0\ncount = 0\nSince S[i] = S[j] ('a' = 'a')\ncount++ => count = 1\nj++ => j= 1\n\ni = 0\nj = 1\nSince S[i] != S[j] ('a' != 'b')\nj++ => j = 2\n\ni = 0\nj = 2\nSince S[i] != S[j] ('a' != 'c')\nj++ => j = 3\n\ni = 0\nj = 3\nSince S[i] = S[j] ('a' = 'a')\ncount++ => count = 2\nj++ => j = 4 \nj reached at end so reset it \ni++ => i = 1\nj = i => j = 1\n\ni = 1\nj = 1\nSince S[i] = S[j] ('b' = 'b')\ncount++ => count = 3\nj++ => j = 2\n\ni = 1\nj = 2\nSince S[i] != S[j] ('b' != 'c')\nj++ => j = 3\n\ni = 1\nj = 3\nSince S[i] != S[j] ('b' != 'a')\nj++ => j = 4\nj reached at end so reset it\ni++ => i = 2 \nj = i => j = 2\n\ni = 2\nj = 2\nSince S[i] = S[j] ('c' = 'c')\ncount++ => count = 4\nj++ => j = 3\n\ni = 2\nj = 3\nSince S[i] != S[j] ('c' != 'a')\nj++ => j = 4\nj reached at end so reset it\ni++ => i = 3\nj = i => j = 3\n\ni = 3\nj = 3\nSince S[i] = S[i] ('a' = 'a')\ncount++ => count = 5\nj++ => j = 4\nj reached at end so reset it \ni++ => i = 4\nj = i => j = 4\nj is still at end so terminate and return count \n\nResultant count is 5<\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t