DWW19H - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ankush Khanna

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a string S and an integer N, a string S^{\prime} is formed by concatenating the string S exactly N times. Find the number of "SS" sub-strings in the string S^{\prime}.
S^{\prime} = \underbrace{S + S + \dots + S}_{\text{concatenating} \space N \space \text{times}}

QUICK EXPLANATION:

  • Count the number of "SS" sub-strings in S and multiply this count with N.
  • If S_{1} = S_{|S|} = 'S', then add N - 1 to the count.

EXPLANATION:

For the first sub-task, it is pretty fine to do an actual implementation of what is explained in the problem statement. That is, we can actually go on about making the string S^{\prime} from the string S by combining N copies of S as explained, and then count the number of "SS" sub-strings (which is a trivial task). The constraints are small enough, and we can pass the test set of the first sub-task easily with this naive implementation.

Let’s say K is the number of "SS" sub-strings in S. For the second sub-task, we need to look at some very simple observations:

  • When we join the string S exactly N times to create the string S^{\prime}, then exactly N - 1 junctions are formed. We say that the clubbing of the first and last characters of the string S forms a junction. It is present between every two successive concatenations of S in S^{\prime}.

  • The number of "SS" sub-strings accounting for all non-junction regions in S^{\prime} can be easily given by the formula K \times N.

  • Now, if a junction itself is a sub-string "SS", then we need to add N - 1 to the current count, as there are exactly N - 1 junctions in S^{\prime}. Therefore, the total count becomes K \times N + N - 1 for this case.

Following the above mentioned key points, we can easily compute the required answer in linear time (linear in the length of the string S, because it takes O(|S|) time to compute the number of "SS" sub-strings in S).
Also, we need to take care of possible integer overflow because the answer can be greater than what a 32 bit integer type can accommodate. So use of 64 bit integer becomes necessary here.
(The largest answer, under the given constraints, can be \{(10^{5} - 1) \times 10^{5} + (10^{5} - 1)\}, which is equal to 10^{10} - 1, therefore a 32 bit integer type is not sufficient here)

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        long ans = 0L;
        for (int i = 0; i < (int) s.size() - 1; i++) {
            if (s[i] == 'S' and s[i + 1] == 'S') {
                ans++;
            }
        }
        ans *= n;
        if (s.front() == s.back() and s.back() == 'S') {
            ans += n - 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

COMPLEXITY:

Time complexity: O(|S|) per test
Space Complexity: O(1) auxiliary space per test

Feel free to share your approach. If you have any queries, they are always welcome.