Problem1-> Maximize Product Operations Solution

Topics Involved / Prerequisites

• String Traversal

• Two Pointers / Index Tracking

Overview

We need to find the shortest contiguous substring that begins with the original first character and ends with the original last character.

By iterating through the string, we can track the most recent index where the required starting character appeared. Whenever we encounter the required ending character, we calculate the substring length from that most recent start and keep the minimum.

Approach

1. Identifying the Targets

The "type" of the string is strictly defined by s[0] and s[n-1]. These are our target starting and ending characters. Our goal is to find the absolute shortest distance between any valid appearance of this start character and a subsequent appearance of this end character.

2. Tracking and Minimizing

We loop through the string from left to right, maintaining a lastSeenStart index. Every time we see our target start character, we update this index to the current position, ensuring it is as far right (and thus as close to the upcoming end character) as possible. If the current character is our target end character, and we have safely seen a start character previously, we calculate the length: current_index - lastSeenStart + 1. We track the minimum of these lengths. The maximum operations we can perform is simply the original length minus this minimum valid length.

function maxOperations(s):
    n = length of s
    if n <= 1: 
        return 0
        
    firstChar = s[0]
    lastChar = s[n - 1]
    
    lastSeenStart = -1
    minLen = infinity
    
    for i from 0 to n - 1:
       
        if s[i] == lastChar AND lastSeenStart != -1:
            currentLen = i - lastSeenStart + 1
            minLen = min(minLen, currentLen)
            
      
        if s[i] == firstChar:
            lastSeenStart = i
            
    // The maximum operations is removing everything except the minimum valid substring
    return n - minLen

Time Complexity

• Time: O(N) - We traverse the string exactly once from left to right.
• Space: O(1) - Only a few integer variables are used to store indices and lengths.

Problem2 -> Distinct Characters Query Solution

Topics Involved / Prerequisites

• Segment Trees

• Bit Manipulation (Bitmasks)

• Range Queries

Overview

Since the string only contains lowercase English letters, any substring's unique characters can be perfectly represented as a 26-bit integer mask. A Segment Tree allows us to efficiently manage these bitmasks, where each parent node is simply the bitwise OR of its two children. This provides rapid point updates to change characters and rapid range queries to count the distinct set bits in any given segment.

Approach

1. The Bitmask Representation Instead of using heavy Hash Sets, we use a single 32-bit integer. If the character is 'a', we set the 0th bit (1 << 0). If it's 'c', we set the 2nd bit (1 << 2). When we combine two segments of a string together, the unique characters of the combined string is just the bitwise OR (|) of their individual integer masks.

2. The Segment Tree We build a Segment Tree where every leaf node holds the bitmask for a single character.

• Updates (Type 1): We navigate down to the leaf representing pos, update its bitmask to the new character val, and then recalculate the parent nodes on the way back up using the bitwise OR operation.

• Queries (Type 2): We fetch the combined bitwise OR mask for the exact range [L, R]. Once we have the final mask, we simply count how many bits are set to 1 (using a built-in popcount function) to get the number of distinct characters!

Code Implementation (Pseudocode)

// Helper function to build the tree initially
function build(node, start, end, data, tree):
    if start == end:
     
        charIndex = ASCII(data[start]) - ASCII('a')
        tree[node] = (1 << charIndex)
    else:
        mid = start + (end - start) / 2
        build(2 * node, start, mid, data, tree)
        build(2 * node + 1, mid + 1, end, data, tree)
      
        tree[node] = tree[2 * node] BITWISE_OR tree[2 * node + 1]

// Helper function for Type 1: Point Update
function update(node, start, end, idx, val, tree):
    if start == end:
      
        tree[node] = (1 << (val - 1))
    else:
        mid = start + (end - start) / 2
        if start <= idx AND idx <= mid:
            update(2 * node, start, mid, idx, val, tree)
        else:
            update(2 * node + 1, mid + 1, end, idx, val, tree)
        tree[node] = tree[2 * node] BITWISE_OR tree[2 * node + 1]

// Helper function for Type 2: Range Query
function query(node, start, end, L, R, tree):
    if R < start OR end < L:
        return 0 // Out of bounds returns an empty mask
        
    if L <= start AND end <= R:
        return tree[node] // Completely inside bounds
        
    mid = start + (end - start) / 2
    leftMask = query(2 * node, start, mid, L, R, tree)
    rightMask = query(2 * node + 1, mid + 1, end, L, R, tree)
    
    return leftMask BITWISE_OR rightMask

// Main Function
function processQueries(data, queries):
    n = length of data
    create array 'tree' of size 4 * n
    
    build(1, 0, n - 1, data, tree)
    create empty array 'results'
    
    for each q in queries:
        if q.type == 1:
            // Point update (converting 1-based pos to 0-based for tree)
            pos = q.pos - 1
            update(1, 0, n - 1, pos, q.val, tree)
        else if q.type == 2:
            // Range query (converting 1-based L, R to 0-based)
            L = q.L - 1
            R = q.R - 1
            mask = query(1, 0, n - 1, L, R, tree)
            // countSetBits counts the number of 1s in the binary representation
            results.push_back(countSetBits(mask))
            
    return results