{"id":1192,"date":"2020-06-10T14:47:47","date_gmt":"2020-06-10T14:47:47","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1192"},"modified":"2020-06-10T14:48:27","modified_gmt":"2020-06-10T14:48:27","slug":"distint-concat","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/distint-concat\/","title":{"rendered":"Distint Concat"},"content":{"rendered":"

Concepts Used<\/h4>\n
\n

String<\/p>\n<\/blockquote>\n

Difficulty Level<\/h4>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h4>\n
\n

Find the total number of substrings which are the concatenation of the same strings, e.g.PP if formed by concatenating P twice.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n1\nxyzxyzxyz\n\nOutput:\n3\n\nExplanation:\nHere we can see 'xyz' repeats twice at index 0 and 3 satisfying our requirements.\n\n'yzx' repeats twice at index 1 and 4 satisfying our requirements.\n\n'zxy' repeats twice at index 2 and 5 satisfying our requirements.\n\nSo, there are a total of 3 strings which makes a substring of form PP where P is required substring. So, 3 is the answer.<\/code><\/pre>\n
Solving Approach :<\/h4>\n
Bruteforce Approach:<\/p>\n
\n
1) In the naive approach, we can find all possible substrings of the given string and also notice their starting point. Then we check if give substring appears twice serial wise from the given index or not. If yes, we count the substring, else we move to the next substring.
\n2) This approach takes O(N^{2})<\/code> to find all substrings where N<\/code> is the length of the given string. For each substring, it again takes O(2\\times N)<\/code> for matching its appearance. So, it totally takes O(N^{3})<\/code> time to process the whole string.
\n3) O(N^{3})<\/code> is very inefficient for string of size larger than 250<\/code>. But our constraints give larger string than it, so we move to a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/p>\n
\n
1) We can find the total number of such substrings if we can count substrings which start from every character of the string.
\n2) For every character, we check if substring from start to current character (Let’s say K<\/code>) is the same as substring starting from current character to following characters of the same length as K<\/code>.
\n3) If both strings are the same, we’have found one such required substring, thus we check if this substring has already been identified or not, if yes, we skip, else we count it as a unique substring.
\n4) We continuously check this for substrings starting from start to current character, and for all characters in the string.<\/p>\n<\/blockquote>\n
Example and Video References<\/h2>\n
Disecho Solution (Youtube)<\/a><\/p>\n
Solutions<\/h2>\n\t\t\t\t\t\t