统计以A开头B结尾的子串数量：算法实现与优化问询

Hey there! Let's tackle this problem of counting substrings that start with 'A' and end with 'B'—I’ve messed around with similar string challenges before, so I’ll walk through both the brute-force method you mentioned and a much more efficient reverse-traversal approach.

Problem Overview #

Given a string, we need to count all valid substrings where the first character is 'A' and the last is 'B'. For example, in the string CABAAXBYA, there are 4 valid substrings:

• AB (positions 1-2)
• AB (positions 1-6)
• AB (positions 3-6)
• AB (positions 4-6)

Brute-Force Approach (Your Initial Idea) #

Your initial brute-force method is totally reasonable for getting started—it's straightforward and easy to understand. Here's how it works:

• Use an outer loop to iterate through every character in the string.
• Whenever you hit an 'A', launch an inner loop to check every character that comes after this 'A'.
• Each time you find a 'B' in the inner loop, increment your total count.

Here's what that looks like in Python code:

def count_ab_substrings_brute(s):
    total = 0
    str_length = len(s)
    for i in range(str_length):
        if s[i] == 'A':
            # Check all characters after this 'A' for 'B's
            for j in range(i + 1, str_length):
                if s[j] == 'B':
                    total += 1
    return total

# Test with your example string
sample_str = "CABAAXBYA"
print(count_ab_substrings_brute(sample_str))  # Output: 4

The catch here is the time complexity: O(n²). This works fine for small strings, but it gets really slow as the string size grows—definitely not ideal for large datasets.

Optimized Approach: Reverse Traversal #

The smarter method you hinted at—traversing from right to left—cuts the time complexity down to O(n) (a single pass through the string). Here's the core logic:

• As we iterate from the end of the string to the start, we keep a running count of how many 'B's we've seen so far.
• Every time we encounter an 'A', we add our current 'B' count to the total. Why? Because this 'A' can form a valid substring with every 'B' that comes after it.

Let's walk through your example string CABAAXBYA step by step to see this in action:

1. Start at the last character ('A'): no 'B's counted yet, total remains 0.
2. Next character ('Y'): still no 'B's, total stays 0.
3. Next character ('B'): increment our b_count to 1, total remains 0.
4. Next character ('X'): b_count stays 1, total stays 0.
5. Next character ('A'): add b_count (1) to total → total becomes 1.
6. Next character ('A'): add b_count (1) to total → total becomes 2.
7. Next character ('B'): increment b_count to 2, total stays 2.
8. Next character ('A'): add b_count (2) to total → total becomes 4.
9. First character ('C'): no change, total stays 4.

Perfect—this matches the expected result of 4!

Here's the optimized code:

def count_ab_substrings_optimized(s):
    total = 0
    b_count = 0
    # Traverse the string from right to left
    for char in reversed(s):
        if char == 'B':
            b_count += 1
        elif char == 'A':
            total += b_count
    return total

# Test with your example string
sample_str = "CABAAXBYA"
print(count_ab_substrings_optimized(sample_str))  # Output: 4

This approach is way more efficient, especially for large strings, since we only loop through the string once with no nested loops.

内容的提问来源于stack exchange，提问作者bleedblue30