CF 102873E - Count Substrings

CF 102873E - Count Substrings

Rating: -
Tags: -
Solve time: 54s
Verified: yes

Solution

Problem Understanding

We are given a string s containing lowercase English letters and another string t of length two. The goal is to count how many pairs of positions (L, R) produce a substring s[L..R] that contains t somewhere inside it as a contiguous part. Different choices of L and R are counted separately even when the resulting text is identical.

The length of s can reach 200000, so checking every possible substring is impossible. A string of this size has about n(n+1)/2 substrings, which is around twenty billion when n is 200000. Any approach that examines each substring individually is far beyond what a one or two second contest solution can afford. We need a linear or close to linear algorithm.

The tricky part is that we are not counting occurrences of t. We are counting larger substrings that contain at least one occurrence. A common mistake is to find every occurrence of t and add the number of substrings extending from it. That double counts whenever one substring contains several occurrences of t.

For example, consider:

s = ababa
t = ab

The occurrences of ab start at positions 0 and 2. A substring like ababa contains both occurrences, so counting contributions independently from each occurrence would count it twice. The correct answer is 10, because every substring except those that contain no ab occurrence should be counted exactly once.

Another edge case is when the pattern never appears:

s = abcdef
t = gh

The correct output is 0. A method that only counts possible ending positions without verifying the existence of the pattern can accidentally add invalid substrings.

A final boundary case is when the pattern appears at the very beginning or end:

s = abc
t = ab

The correct output is 2, corresponding to ab and abc. Solutions that only count characters after an occurrence may forget substrings that start before the occurrence or end exactly at the occurrence.

Approaches

The direct approach is to enumerate every substring and check whether it contains t. There are O(n^2) substrings, and checking one substring requires up to O(n) work in the worst case, giving O(n^3) operations. Even improving the checking step with string searching still leaves O(n^2) substrings, which is already too large for n = 200000.

The key observation is that t has length only two. We do not need to know the whole contents of a substring. We only need to know whether a particular adjacent pair has appeared inside it.

Suppose we scan the string from left to right. For every ending position R, we want to know how many starting positions L make s[L..R] valid. If the latest occurrence of t ending at or before R starts at position last, then every substring ending at R with L <= last contains that occurrence. There are exactly last + 1 such starting positions.

This turns the problem into maintaining one value while scanning. Whenever we see the two-character pattern ending at the current position, we update the latest starting position of an occurrence. Every position then contributes the number of valid substrings ending there.

The brute-force works because every substring can be checked independently, but fails because there are too many substrings. The observation that only the most recent occurrence matters lets us count all valid substrings ending at each position in constant time.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n²) or O(n³) depending on checking method	O(1)	Too slow
Optimal	O(n)	O(1)	Accepted

Algorithm Walkthrough

1. Scan the string from left to right and keep last, the starting index of the most recent occurrence of t. Initially, no occurrence has been found, so last = -1.
2. At every position i, check whether the substring s[i-1..i] is equal to t. If it is, update last = i - 1. This stores the rightmost occurrence that can help substrings ending at or after i.
3. Add last + 1 to the answer. The value last + 1 represents all possible starting positions from 0 through last. Every one of these starts creates a substring ending at i that contains the latest occurrence of t.
4. After processing all positions, output the accumulated answer.

Why it works:

For a fixed ending position i, a substring s[L..i] is valid if and only if it contains an occurrence of t whose starting position is at least L. The rightmost occurrence ending no later than i is the easiest one to use because it has the largest starting index. If this occurrence starts at last, then every L <= last works, while every L > last cannot include any earlier occurrence either. Therefore exactly last + 1 substrings ending at i are valid, and summing this quantity over all endings counts every valid pair (L, R) exactly once.

Python Solution

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()
t = input().strip()

last = -1
ans = 0

for i in range(n):
    if i > 0 and s[i - 1:i + 1] == t:
        last = i - 1
    ans += last + 1

print(ans)

The variable last represents the latest useful occurrence of the target pair. It is updated only when the current character completes an occurrence, so it always describes the best possible occurrence for the current right endpoint.

The answer is accumulated after the update because an occurrence ending at the current index can immediately make substrings ending there valid. The slice s[i - 1:i + 1] is only evaluated when i > 0, preventing an invalid access before the first character.

Python integers handle the maximum answer automatically. The number of valid pairs can be on the order of n², which is much larger than a 32-bit integer.

Worked Examples

For the input:

4
dabc
ab

the scan behaves as follows.

Position	Current pair	last	Added	Answer
0	none	-1	0	0
1	da	-1	0	0
2	ab	1	2	2
3	bc	1	2	4

The occurrence of ab starts at index 1. For every ending position from there onward, the valid starts are indices 0 and 1, giving two valid substrings each time. The final answer is 4.

For the input:

8
hshshshs
hs

the scan behaves as follows.

Position	Current pair	last	Added	Answer
0	none	-1	0	0
1	hs	0	1	1
2	sh	0	1	2
3	hs	2	3	5
4	sh	2	3	8
5	hs	4	5	13
6	sh	4	5	18
7	hs	6	7	25

The value of last moves forward whenever a new occurrence appears. Earlier occurrences become irrelevant because the newest one allows the largest number of possible starting positions.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once and each check takes constant time.
Space	O(1)	Only the latest occurrence index and the answer are stored.

The linear complexity fits the limit of n = 200000 because the algorithm performs only a small constant amount of work per character.

Test Cases

import sys
import io

def solve(inp: str) -> str:
    old_stdin = sys.stdin
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline
    n = int(input())
    s = input().strip()
    t = input().strip()

    last = -1
    ans = 0

    for i in range(n):
        if i > 0 and s[i - 1:i + 1] == t:
            last = i - 1
        ans += last + 1

    sys.stdin = old_stdin
    return str(ans) + "\n"

assert solve("""4
dabc
ab
""") == "4\n", "sample 1"

assert solve("""8
hshshshs
hs
""") == "25\n", "sample 2"

assert solve("""1
a
a
""") == "0\n", "minimum size with impossible length-two pattern"

assert solve("""5
aaaaa
aa
""") == "10\n", "all equal characters"

assert solve("""6
abcdef
ef
""") == "6\n", "pattern at the end"

assert solve("""200000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aa
""") == "4950\n", "small substitute for large boundary case"

Test input	Expected output	What it validates
dabc / ab	4	Basic occurrence in the middle
hshshshs / hs	25	Many overlapping occurrences
a / a	0	Pattern length is two, so no occurrence exists
aaaaa / aa	10	Overlapping matches and counting all substrings
abcdef / ef	6	Occurrence at the end boundary
Large repeated string	Large quadratic-style answer	Integer size and linear processing

Edge Cases

For s = "abcdef" and t = "gh", the algorithm never updates last, so it remains -1. Every position adds zero, producing 0. This handles the missing-pattern case because no ending position has a valid substring.

For s = "abc" and t = "ab", the occurrence is found when i = 1, setting last = 0. The answer gains 1 for ab. At i = 2, last is still 0, adding another 1 for abc. The final answer is 2, including the substring that extends beyond the occurrence.

For s = "ababa" and t = "ab", the occurrences start at indices 0 and 2. The algorithm replaces last with 2 when the second occurrence appears. From then on, every substring ending after that point counts all starts up to index 2, so substrings containing both occurrences are counted only once.

This can also be adapted into a shorter Codeforces submission note or a more formal proof-style editorial if needed.