Find number of contiguous Substrings with repeated patterns
Given a string str consisting of digits, the task is to find the number of contiguous substrings such that the substring can be rearranged into a repetition of some string twice.
Examples:
Input: str=”15512212″
Output: 6
Explanation: Possible 6 substrings are :
- “1551” can be rearranged to “1515“
- “155122” can be rearranged to “152152“
- “551221” can be rearranged to “512512“
- “1221” can be rearranged to “1212“
- “55” can be rearranged to “55“
- “22” can be rearranged to “22“
Input: str=”590025995299005″
Output: 14
Approach: This can be solved with the following idea:
The approach used in the code is based on the observation that if a substring can be rearranged into a repetition of some string twice, then toggling any subset of its digits an even number of times will also result in a substring. This observation is used to efficiently compute the count of substrings using bitwise operations and maps.
Steps to implement the above approach:
- Initialize a map m with key-value pair (0, 1).
- Read the input string str.
- Initialize a variable bb to 0.
- Initialize a variable ret to 0.
- For each character c in str, do the following:
- Convert the character c to integer v by subtracting the ASCII value of ‘0‘ from it.
- Update bb by toggling the v-th bit in bb using the bitwise XOR operation.
- If m[bb] exists, increment ret by m[bb].
- Increment m[bb] by 1.
- Print the value of ret, which is the count of required contiguous substrings.
Below is the implementation of the above approach:
C++
|
Time Complexity: O(n*log(m))
Auxilairy Space: O(m)
Related articles:
Given a string str consisting of digits, the task is to find the number of contiguous substrings such that the substring can be rearranged into a repetition of some string twice.
Examples:
Input: str=”15512212″
Output: 6
Explanation: Possible 6 substrings are :
- “1551” can be rearranged to “1515“
- “155122” can be rearranged to “152152“
- “551221” can be rearranged to “512512“
- “1221” can be rearranged to “1212“
- “55” can be rearranged to “55“
- “22” can be rearranged to “22“
Input: str=”590025995299005″
Output: 14
Approach: This can be solved with the following idea:
The approach used in the code is based on the observation that if a substring can be rearranged into a repetition of some string twice, then toggling any subset of its digits an even number of times will also result in a substring. This observation is used to efficiently compute the count of substrings using bitwise operations and maps.
Steps to implement the above approach:
- Initialize a map m with key-value pair (0, 1).
- Read the input string str.
- Initialize a variable bb to 0.
- Initialize a variable ret to 0.
- For each character c in str, do the following:
- Convert the character c to integer v by subtracting the ASCII value of ‘0‘ from it.
- Update bb by toggling the v-th bit in bb using the bitwise XOR operation.
- If m[bb] exists, increment ret by m[bb].
- Increment m[bb] by 1.
- Print the value of ret, which is the count of required contiguous substrings.
Below is the implementation of the above approach:
C++
|
Time Complexity: O(n*log(m))
Auxilairy Space: O(m)
Related articles: