Double Strings

Hard
0/120
Average time to solve is 35m
profile
Contributed by
14 upvotes
Asked in company
alibaba

Problem statement

You are given a string ‘STR’, containing only lowercase English letters.

Your task is to determine the total number of distinct substrings present in ‘STR’ which are double strings.

Note : 
1. A double string is a string that is made by concatenation of some string with itself.

2. The length of a double string is at least 2.

For example :

In the string ‘ababab’, there are just two substrings, that are double strings. Both such substrings are ‘abab’, and thus there exists only one distinct substring which is a double string. ‘abab’ can be written as ‘ab’ + ‘ab’. But ‘ababab’ can not be considered as a double string because ‘ab’ has been concatenated twice with itself.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains the string ‘STR’.
Output Format : 
For each test case, print a single integer, denoting the total number of distinct substrings which are also double strings.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= |STR| < 2000
Where ‘T’ denotes the number of test cases and |STR| represents the length of the string ‘STR’

Time Limit: 1sec
Sample Input 1 :
1
abcarcar
Sample Output 1 :
1
Explanation for sample input 1 :
In this test case, we can observe that the substring ‘carcar’ can be written as ‘car’ + ‘car’. So, ‘carcar’ is a double substring. Since, this is the only such substring, we print 1.
Sample Input 2 :
1
abbasdasda
Sample Output 2 :
3
Explanation for sample input 2 :
In this case, the substring ‘bb’ can be written as ‘b’ + ‘b’. ‘sdasda’ can be written as ‘sda’ + ‘sda’ and ‘asdasd’ can be written ‘asd’ + ‘asd’. So, a total of 3 substrings exist in the given string which are double strings.
Hint

Find out all substrings of even length

Approaches (3)
Brute Force Approach

Approach:

The approach of this problem is to find out all substrings of even length because for any string to be a double string, it must be of even length. For checking whether a substring is a double string or not, simply check whether all the characters in the first half of the string are equal to the corresponding characters in the second half or not. 

 

Steps:

  1. Declare an unordered set, say allDistinctStrings, to store the distinct substrings.
  2. Store the size of the string ‘STR’ as strLen.
  3. Run a loop from i=0 to i<strLen-1, and do:
    1. Run another loop for every even value of len from len=2 to len<=strLen-i, and do:
      1. Define substring as the substring starting at ‘ith’ index having a length ‘len’. Formally, make substring = s.substr(i,len).
      2. Now, if isDoubleString(substring == true), this means that the substring starting at index ‘i’ having a length of ‘len’ is a double string. Hence, we insert it into the set allDistinctStrings.
  4. Finally, the total number of distinct double substrings will be equal to the size of this set as this set does not contain any duplicate string. So, we return the size of this set.

void isDoubleString(string str) {

  1. Define mid as str.size /2 .
  2. Run a loop from i=0 to i<mid, and do:
    1. If the character at ith index in the first half of the string is not equal to the ith index in the second half, then it is not a double string. Formally, if str[i] != str[mid+i], return false.
  3. If all the corresponding characters match, return true as this is a double string.
Time Complexity

O(N^3), where N is the length of the string.

 

We are finding all substrings in O(N^2) time, and for each substring, we are traversing it entirely to check whether it is a double substring or not. This takes another O(N) time for each substring. So, our overall complexity becomes O(N^3).

Space Complexity

O(N), where N is the length of the given string.

 

We are extra linear space to maintain the set in which all the distinct substrings are getting stored

Code Solution
(100% EXP penalty)
Double Strings
Full screen
Console