Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
1.1.
Input
1.2.
Output
1.3.
Constraints
1.4.
Example
1.4.1.
Input
1.4.2.
Output
2.
Solution Approach
2.1.
Method 1: Naive Approach
2.2.
Method 2: O(n2)
2.3.
Method 3: Hashing + Binary Search
2.3.1.
C++ implementation
2.3.2.
Complexities
3.
Frequently Asked Questions
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Tandem

Author Manan Singhal
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Problem Statement

A tandem is a non-empty string repeated three times, like AAA for a non-empty string A. A tandem is interesting if the characters who follow A's incident aren't the same; otherwise, it's boring. How many interesting and boring tandems does a string s have?

Also see, kth largest element in an array and  Euclid GCD Algorithm

Input

There is only one test case available.

A string s appears on the first line of the input.

Output

The result should have only one line with two space-separated integers indicating the string's number of interesting and boring tandems.

Constraints

  • 1 ≤ |s| ≤ 200000
  • s consists of lower case English alphabets a to z.

Example

Input

abaaabaaabaaabbbb

Output

5, 3

Solution Approach

Method 1: Naive Approach

We count how many intriguing and uninteresting tandems there are per length of A. Let's pretend that |A| equals L. As a result, the tandem's length is 3L.

Consider the numbers 0, L, 2L, 3L, and so on. Three of these roles will be covered by a 3L tandem. So (i,j,k) = (i,i+L,i+2L).

  • The length of the longest prefix of s[i...N-1], s[j...N-1], and s[k...N-1] is LCP(i,j,k).
  • The length of the longest suffix of s[0...i], s[0...j], and s[0...k] is LCS(i,j,k).


Let V = min(LCS(i,j,k),L) + min(LCP(i,j,k),L) - 1. Then:

  • If V < L implies there are no tandems.
  • If V≥L and LCP(i,j,k)>L, there are 0 interesting tandems and V−L+1 boring tandems.
  • If V≥L and LCP(i,j,k)≤L, then there are one interesting tandem and V−L boring tandems.

Method 2: O(n2)

Let's count how many tandems there are based on A's length. Assuming A=L, the tandem AAA is 3L long. For the time being, let's correct this L and then count all boring and fascinating 3L tandems. Our solution should be fast enough to allow us to execute this for each L[1, N/3].

Consider the letters s0, sL, s2L, s3L, etc.

There are about N/L positions like this. However, because L characters separate these, any tandem of length 3L covers exactly three of them. As a result, let's fix three nearby characters, say si, sj, sk, where (i,j) and (j,k) are separated by L characters, and then count all boring and interesting tandems that span these three.

The tandem must begin at some point in [iL+1, i]. Otherwise, it will not be able to cover si if it starts at some point i, and it will not be able to cover sk if it starts at some location iL. But it can't simply begin at any point! If we want the string sa,a+3L-1 to be tandem, we must ensure that the following conditions are met (by definition):

sa,a+L−1 sa+L,a+2L−1sa+2L,a+3L−1

However, because of how we choose to position a, we get a≤i≤a+L-1, a+L≤j≤a+2L-1, and a+2Lka+3L-1. It indicates that the equality above can be broken down into two parts:

sai sa+L,jsa+2L,k

si,a+L−1 sj,a+2L−1sk,a+3L−1

These two equalities can be stated in a different ways. The first is identical to:

A common suffix of length i-a+1 must be shared by the strings s0,i,s0,j, and s0,k.

The second is the same as the first:

A common prefix of length a+L-i must exist between the strings si, N-1, sj, N-1, and sk, N-1.

This allows us to calculate the number of tandems that cover si sj, and sk. First, let's define two terms:

  • The length of the longest prefix of si, N-1, sj, N-1, and sk, N-1 is LCP(i,j,k).
  • The length of the longest suffix of s0,i,s0,j, and s0,k is LCS(i,j,k).


Min(LCS(i,j,k),L) and min(LCP(i,j,k),L) each take O(L) time to compute. The running time is O(N/L.L)=O(N) per L since we will do this about N/L times for each length L. As a result, the running time for each L[1, N/3] is O(N2).

Method 3: Hashing + Binary Search

Compare any two substrings in O(1) time. We can use binary search to speed up the computation of LCP and LCS. Hashing is one approach to performing quick substring comparisons.

Polynomial hashing will be used specifically. A base B and a modulus M are set. Now we'll define H, the hash function (S). For the string s = s0s1s2.

H(s)=(v(s0)+v(s1)B1+v(s2)B2+v(s3​)B3+…+v(sN−1)BN−1) mod M

where, v(c) is a character-to-number mapping function.

This hash will be used to compare substrings in O(1):

  • Preprocess the text so that H(s) for every substring s can be computed in O(1) time.
  • Compare their hashes, H(t) and H(s), to compare two substrings, s and t.


When two strings are equal, their hashes must also be identical. Unfortunately, even if they are not equal, the hashes may be identical. As a result, this hashing algorithm occasionally fails. However, wisely choosing B, M, and v(c) will most likely be accepted.

So, how do we prepare the string for use? The following are the main advantages of using polynomial hashing:

  • Concatenation: Given H(s), H(t) and H(st) can be computed in O(1) time as H(st) = (H(s) + H(t)B|s|)mod M.
  • Splitting: Given H(st), H(t) and H(s) can be computed in O(1) time as H(s) = (H(st) - H(t)B|s|)mod M.


These are the attributes that can be used to preprocess. We compute the hashes of all the string's prefixes. Using the concatenation property may be done in O(N) time. Then, to compute the hash, identify the necessary suffixes st and t, then use the splitting property to compute H(s) from H(st) and H(t)!

C++ implementation

/* C++ implementation */

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second

using namespace std;
/* Variables */
const int N = 2e3+5;
const int M = 1e2+2;
const int mod = 1e9+7;
const ll base = 751;
const int inf = 1e9;
/* Calling variables */
int m, n, t, d[N], lab[N];
int k, a[N], sum[N];
ll ans, tong, b[N];
vector<int> adj[N];
vector<pii> vi;
string s;
bool vis[N];
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n&1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
/* Creating addition function with upper limit */
void add(int &x, int y)
{

    x += y;
    if(x >= mod)x -= mod;
}
/* Implementing hashing creating struct */
struct Hash
{
    int n;
    const ll mod = 1e9+7;
    const int base = 521;
    string s;
    vector<ll> a, p;
    
    /* Main class inside struct */
    Hash(string _s)
    {
        s = _s;
        n = s.length();
        a.resize(n+1);
        p.resize(n+1);
        a[0] = 0;
        p[0] = 1;
        for(int i = 1; i <= n; i ++)
        {
            a[i] = (1ll*a[i-1] * base % mod + b[s[i-1]-'a']) % mod;
            p[i] = 1ll*p[i-1]*base%mod;
        }
    }
    
    /* Returning function inside struct */
    int get(int l, int r)
    {
        return 1ll*(a[r]-a[l-1]*p[r-l+1]%mod+mod)%mod;
    }

    /* Retrieving LCP value */
    int lcp(int u, int v)
    {
        int l = 1, r = min(v, n-u-v*2+1), mid;
        while(l <= r)
        {
            mid = (l+r)>>1;
            t = get(u, u+mid-1);
            if(t == get(u+v, u+v+mid-1) && t == get(u+v*2, u+v*2+mid-1))l = mid+1;
            else r = mid-1;
        }
        return r;
    }
    
    /* Retrieving LCS value */
    int lcs(int u, int v)
    {
        int l = 1, r = min(v, u), mid;
        while(l <= r)
        {
            mid = (l+r)>>1;
            t = get(u-mid+1, u);
            if(t == get(u+v-mid+1, u+v) && t == get(u+v*2-mid+1, u+v*2))l = mid+1;
            else r = mid-1;
        }
        return r;
    }
};
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

/* Main algo function */
void sol()
{
    cin >> s;
    for(int j = 0; j < 26; j ++)b[j] = mt() % mod;
    n = s.length();
    Hash pre(s);
    ll res1 = 0, res2 = 0;
    int l, r;
    for(int i = 1; i*3 <= n; i ++)
    {
        for(int j = 1; j <= n-i*2+1; j += i)
        {
            l = pre.lcp(j, i);
            r = pre.lcs(j, i);
            k = l+r-i;
            if(k <= 0)continue;
            /* cout << j <<" "<<i<<" "<<l<<'\n'; */
            l = j-(i-l);
            if(l+i*3 > n || s[l-1] != s[l+i*3-1])
            {
                res1 += 1;
                res2 += k-1;
            }
            else res2 += k;
        }
    }
    cout << res1 <<" "<<res2;
}

/* Main Code */
int main()
{
    /* Getting value */
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
    int test = 1;
    /* Running sol function and showing values */
    while(test -- > 0)sol();
    return 0;
}

Input

abaaabaaabaaabbbb

Output

5, 3

Complexities

Time complexity
O(N log2N)
Reason: LCP and LCS are computed with binary search, which takes O(log N) time each, so doing that N/L times gives O(N/LlogN), which on calculation gives O(N log2N).

 

Space complexity
O(N)
Reason: Implementing binary search and to display we need a vector of size N.
Check out this problem - Maximum Product Subarray

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

  1. What is Hashing?
    Hashing utilizes algorithms to transform any size input into a fixed-size integer or text.
     
  2. What is String Hashing?
    String hashing is the most efficient way to convert a string into a whole number, known as a hash of that string.
     
  3. What is the purpose of String Hashing?
    The optimum hashing is the one that has the fewest chances of crashing (i.e., in two unique strings having a similar hash).
     
  4. What Does String Hashing's Time and Space Complexity Mean?
    Time complexity: O(N)
    Space complexity: O(1)
     
  5. What are some examples of Hashing applications?
    Calculation of Rabin-Karp.
    Count the number of substrings that can create from the string.
    Counting the number of palindrome substrings.

Key Takeaways

In this article, we have solved the Tandem problem using the C++ language. We hope that this question will help you understand the application of hashing and binary search.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Previous article
Find maximum average subarray of length k
Next article
Substrings and Frequency
Live masterclass