Code

Python

def numberOfWays(book: str) -> int:
    n = len(book)
    # Precompute the number of '0's and '1's to the left and right of each position    left_zeros = [0] * n
    left_ones = [0] * n
    right_zeros = [0] * n
    right_ones = [0] * n
    # Fill left_zeros and left_ones    for i in range(1, n):
        left_zeros[i] = left_zeros[i - 1] + (1 if book[i - 1] == '0' else 0)
        left_ones[i] = left_ones[i - 1] + (1 if book[i - 1] == '1' else 0)
    # Fill right_zeros and right_ones    for i in range(n - 2, -1, -1):
        right_zeros[i] = right_zeros[i + 1] + (1 if book[i + 1] == '0' else 0)
        right_ones[i] = right_ones[i + 1] + (1 if book[i + 1] == '1' else 0)
    # Count the number of valid triplets    total_ways = 0    for i in range(1, n - 1):
        if book[i] == '0':
            # Middle page is '0', we want '1' on both sides            total_ways += left_ones[i] * right_ones[i]
        else:
            # Middle page is '1', we want '0' on both sides            total_ways += left_zeros[i] * right_zeros[i]
    return total_ways

OR

def bookmarks(pages, k):
    pages = list(pages)
    bookmarks = [[0 for _ in range(2)] for _ in range(k+1)] # bookmarks[length][starting_with]    bookmarks[0][0]=1    bookmarks[0][1]=1    for i in range(len(pages)-1,-1,-1):
        if pages[i] == 0:
            for length in range(k,0,-1):
                bookmarks[length][0]+=bookmarks[length-1][1]
        else:
            for length in range(k,0,-1):
                bookmarks[length][1]+=bookmarks[length-1][0]
        return sum(bookmarks[k])

OR

def bookmarks(pages, k):
    pages = [int(p) for p in pages]  # Ensure pages are integers 0 and 1    bookmarks = [[0 for _ in range(2)] for _ in range(k + 1)]
    # We start with a "virtual" sequence of length 0 that can end with either 0 or 1    bookmarks[0][0] = 1    bookmarks[0][1] = 1    # Iterate over the pages from right to left    for i in range(len(pages) - 1, -1, -1):
        if pages[i] == 0:
            # Update DP for sequences that end with '0'            for length in range(k, 0, -1):
                bookmarks[length][0] += bookmarks[length - 1][1]
        else:
            # Update DP for sequences that end with '1'            for length in range(k, 0, -1):
                bookmarks[length][1] += bookmarks[length - 1][0]
    # The result is the sum of valid sequences of length `k` that end with '0' or '1'    return sum(bookmarks[k])
# Example usage:book = "01001"result = bookmarks(book, 3)
print(result)  # Expected output: 4

![[amazon-question-find-the-longest-substring-with-the-first-v0-4wgfakznw8wd1.webp]]