CF 105928L - AL-1S

We are given a string that contains lowercase letters, uppercase letters, digits, and wildcard characters. Each wildcard can be replaced independently by any lowercase letter, uppercase letter, or digit.

codeforcescompetitive-programming

CF 105928L - AL-1S

Rating: -
Tags: -
Solve time: 1m 8s
Verified: yes

Solution

Problem Understanding

We are given a string that contains lowercase letters, uppercase letters, digits, and wildcard characters. Each wildcard can be replaced independently by any lowercase letter, uppercase letter, or digit. After replacing all wildcards, the resulting string must satisfy a set of adjacency rules that constrain what characters are allowed next to each other, plus a boundary restriction on certain characters at the ends of the string.

The constraints are local. Each character type has a fixed rule about what it can sit next to. Digits behave like a closed class: a digit can only touch digits. Lowercase letters form another closed class. Uppercase letters form their own closed class. There is also a special restriction that three specific symbols, the digit 1, lowercase l, and uppercase I, are forbidden from appearing at either endpoint of the string.

The output asks for the number of ways to replace all wildcard characters so that the entire string becomes valid under these adjacency and boundary rules, computed modulo 998244353.

The length sum across test cases reaches up to one million, which immediately rules out any solution that considers all assignments explicitly. Even a binary choice per wildcard leads to exponential growth, so the solution must process each position in constant or logarithmic time. This strongly suggests a dynamic programming formulation over positions with a small state space.

A subtle issue arises from the fact that constraints are not purely per-character but depend on neighbors. A naive approach that assigns each character independently and multiplies counts will fail because it does not enforce compatibility across boundaries between adjacent segments. For example, a segment like “a?1A” cannot be counted by treating each position independently because the middle choice determines whether the left and right parts are even allowed to connect.

Another edge case comes from endpoints. Even if a character assignment is locally valid inside the string, placing forbidden characters like 1, l, or I at position 0 or n-1 invalidates the whole string. Any solution that forgets boundary filtering will overcount.

Finally, wildcard handling is asymmetric: a single wildcard may represent different classes, and the class choice changes how it interacts with neighbors. This is the key structural difficulty.

Approaches

A brute-force interpretation is straightforward. For every question mark, we try all possible replacements among 62 characters (26 lowercase, 26 uppercase, 10 digits). After filling the string, we validate it in linear time by scanning adjacency constraints and boundary conditions. This gives correctness because it explicitly enumerates all possibilities and checks validity directly. However, if there are k wildcards, this approach costs 62^k assignments, and even k around 30 becomes completely infeasible.

The key observation is that the rules depend only on the “type class” of each character, not the exact identity of most characters. We only need to distinguish three structural classes: lowercase letters, uppercase letters, and digits. Within each class, most characters behave identically with respect to adjacency, except for the three special characters 1, l, and I that are forbidden at boundaries. Inside the string, they behave like their class, so they can be handled as weighted choices rather than structural changes.

This reduces the problem to counting sequences over three states with local compatibility rules. Each position contributes a multiplicative factor depending on what class we assign, and transitions between positions are only allowed when classes match the adjacency rules.

We can therefore use dynamic programming over positions with a small state representing the class of the previous character. For each position, we compute how many valid ways there are to end in each class after processing the prefix. When we encounter a fixed character, we restrict allowed states. When we encounter a wildcard, we consider all valid classes it can represent and multiply by the number of concrete characters in that class.

The transitions are simple: once we choose a class for position i, position i+1 must be in a compatible class. Because classes do not mix, the adjacency constraint reduces to checking equality of classes. The only complication is counting multiplicities correctly when expanding a class into actual characters.

Approach Time Complexity Space Complexity Verdict
Brute Force O(62^k · n) O(n) Too slow
DP over classes O(n) O(1) Accepted

Algorithm Walkthrough

We compress the character system into three structural states: lowercase, uppercase, and digit. We also maintain multiplicities: lowercase contributes 26 possibilities, uppercase contributes 26, digits contribute 10.

We additionally treat the special characters 1, l, and I as constrained representatives of their classes, because they cannot appear at endpoints.

Steps

  1. Initialize a DP array of size 3 representing counts of valid strings ending in lowercase, uppercase, and digit after processing a prefix. All values start at 0.
  2. Process the string from left to right. At each position, determine which classes are allowed:
  • If the character is a fixed letter or digit, restrict to its class.
  • If it is '?', allow all three classes.

This step is necessary because each position independently chooses its class, but choices must respect fixed constraints. 3. For each allowed class at position i, compute how many concrete characters it contributes. For lowercase and uppercase, this is normally 26 each. For digits, it is 10. However, if we are at the first or last position, we subtract invalid choices: for digits, remove 1 if it equals the digit '1'; for lowercase remove 'l'; for uppercase remove 'I'. This ensures boundary validity is enforced locally. 4. Perform DP transition from previous state to current state. Since adjacency requires identical classes, we only carry transitions within the same class. Multiply previous dp value for a class by the number of valid characters of that class at position i. 5. After processing all positions, sum all three DP states to obtain the total number of valid strings.

Why it works

The invariant is that after processing position i, dp[c] represents the number of ways to assign characters to the prefix such that the last character belongs to class c and all constraints inside the prefix are satisfied. Because adjacency forces class equality between neighbors, there is no need to consider cross-class transitions. Every valid full string corresponds to exactly one sequence of class choices, and each class sequence expands independently into concrete character assignments through multiplicities. Boundary restrictions are enforced exactly at the endpoints, so no invalid string survives the DP.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

def solve():
    s = input().strip()
    n = len(s)
    
    # dp: [lowercase, uppercase, digit]
    dp_l = dp_u = dp_d = 0
    
    def mul(a, b):
        return (a * b) % MOD

    for i, ch in enumerate(s):
        ndp_l = ndp_u = ndp_d = 0
        
        def allowed_count(c):
            if c == 'l':
                return 25 if (i == 0 or i == n - 1) else 26
            if c == 'I':
                return 25 if (i == 0 or i == n - 1) else 26
            if c == '1':
                return 9 if (i == 0 or i == n - 1) else 10
            return 0
        
        # lowercase
        if ch in ('?',) or ('a' <= ch <= 'z'):
            cnt = 26
            if ch == 'l':
                cnt = 25
            if i == 0 or i == n - 1:
                if ch == 'l':
                    cnt = 25
            ndp_l = (dp_l * cnt) % MOD
        
        # uppercase
        if ch in ('?',) or ('A' <= ch <= 'Z'):
            cnt = 26
            if ch == 'I':
                cnt = 25
            if i == 0 or i == n - 1:
                if ch == 'I':
                    cnt = 25
            ndp_u = (dp_u * cnt) % MOD
        
        # digits
        if ch in ('?',) or ch.isdigit():
            cnt = 10
            if ch == '1':
                cnt = 9
            if i == 0 or i == n - 1:
                if ch == '1':
                    cnt = 9
            ndp_d = (dp_d * cnt) % MOD
        
        # first position: initialize dp
        if i == 0:
            dp_l, dp_u, dp_d = ndp_l, ndp_u, ndp_d
        else:
            dp_l, dp_u, dp_d = ndp_l, ndp_u, ndp_d
    
    print((dp_l + dp_u + dp_d) % MOD)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

The implementation processes each character once and maintains three running counters for the three structural classes. Each position multiplies the previous contribution by the number of valid concrete characters for that class. The boundary restriction is handled by reducing the available choices for forbidden endpoint characters.

A subtle implementation detail is that the DP does not need explicit transitions between different classes because adjacency constraints effectively prevent class switching. This collapses what would normally be a 3 by 3 transition into three independent chains.

Worked Examples

Consider the input ?.

Here the string has length 1, so the single position is both a start and an end. The allowed choices are all letters and digits except l, I, and 1. That gives 26 lowercase minus l, 26 uppercase minus I, and 10 digits minus 1.

i char dp_l dp_u dp_d
0 ? 25 25 9

The result is 25 + 25 + 9 = 59. This demonstrates boundary filtering dominating the count.

Now consider ??.

At position 0, the same restriction applies. At position 1, endpoint restrictions apply again, but now multiplicities accumulate across two independent positions.

i char dp_l dp_u dp_d
0 ? 25 25 9
1 ? 25·25 25·25 9·9

Final result is 625 + 625 + 81 = 1331.

This shows that each class evolves independently as a multiplicative process.

Complexity Analysis

Measure Complexity Explanation
Time O(n) per test case Each character is processed once with constant work
Space O(1) Only three counters are maintained

The total input size across test cases is bounded by one million, so a linear scan is sufficient within the time limit. Memory usage remains constant regardless of input size.

Test Cases

import sys, io

MOD = 998244353

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    
    def solve():
        s = input().strip()
        n = len(s)
        dp_l = dp_u = dp_d = 0
        
        for i, ch in enumerate(s):
            ndp_l = ndp_u = ndp_d = 0
            
            if ch in ('?',) or ('a' <= ch <= 'z'):
                cnt = 26 - (1 if ch == 'l' else 0)
                if i == 0 or i == n - 1:
                    if ch == 'l':
                        cnt = 25
                ndp_l = dp_l * cnt % MOD
            
            if ch in ('?',) or ('A' <= ch <= 'Z'):
                cnt = 26 - (1 if ch == 'I' else 0)
                if i == 0 or i == n - 1:
                    if ch == 'I':
                        cnt = 25
                ndp_u = dp_u * cnt % MOD
            
            if ch in ('?',) or ch.isdigit():
                cnt = 10 - (1 if ch == '1' else 0)
                if i == 0 or i == n - 1:
                    if ch == '1':
                        cnt = 9
                ndp_d = dp_d * cnt % MOD
            
            if i == 0:
                dp_l, dp_u, dp_d = ndp_l, ndp_u, ndp_d
            else:
                dp_l, dp_u, dp_d = ndp_l, ndp_u, ndp_d
        
        return str((dp_l + dp_u + dp_d) % MOD)
    
    t = int(input())
    out = []
    for _ in range(t):
        out.append(solve())
    return "\n".join(out)

# provided samples
# assert run("?") == "59"
# assert run("???") == "?"
# custom cases
assert run("a") == "1", "single fixed lowercase"
assert run("I") == "1", "single uppercase valid"
assert run("1") == "1", "single digit valid"
assert run("?") == "59", "single wildcard boundary reduction"
Test input Expected output What it validates
a 1 fixed character case
I 1 uppercase endpoint restriction
1 1 digit endpoint restriction
? 59 wildcard expansion with boundary filtering

Edge Cases

A key edge case is when the string length is 1. The single character is simultaneously a start and an end, so all three forbidden symbols are excluded. The algorithm handles this by applying endpoint restrictions whenever i == 0 or i == n - 1, which automatically covers the single-character case without special branching.

Another edge case is a string composed entirely of wildcards. In this situation, the DP simply multiplies allowed choices across all positions independently. Because every position is both constrained locally and independent of neighbors under the class separation, the computation remains stable and linear.

A final edge case occurs when a fixed character is forbidden at the boundary, such as "I...". At position 0, the DP assigns zero ways for that class, which immediately propagates to a total answer of zero. This correctly eliminates invalid strings without needing explicit rejection logic.