Minimum Operations to Make a Special Number - Video Solutions

Problem Overview: You are given a numeric string and can delete any digits. The goal is to make the remaining number special, meaning it is divisible by 25. The task is to compute the minimum number of deletions required.

A number is divisible by 25 only if its last two digits are 00, 25, 50, or 75. That observation converts the problem into finding the cheapest way to keep a subsequence that ends with one of these four patterns.

Approach 1: Greedy Using Two-Pointer Technique (O(n) time, O(1) space)

The greedy insight is that only the final two digits determine divisibility by 25. Scan the string from right to left and try to form one of the valid endings: 00, 25, 50, or 75. Use two pointers: the first pointer searches for the last digit of the pair, and once found, the second pointer scans left to find the matching preceding digit. Every skipped character represents a deletion.

Compute the deletion cost for each of the four valid endings and keep the minimum. This works because keeping the rightmost valid pair always minimizes deletions to the right side of the string. The algorithm performs only linear scans over the string and uses constant extra memory. Concepts used here commonly appear in greedy and string problems.

Approach 2: Dynamic Programming Subsequence Search (O(n * k) time, O(k) space)

Another perspective treats the task as a subsequence matching problem. The valid endings form a small set of patterns: ["00", "25", "50", "75"]. For each pattern, run a dynamic programming or subsequence scan that tracks how many characters you must delete to keep the pattern in order.

Iterate through the string and attempt to match the pattern characters sequentially. If the current digit matches the next required character in the pattern, advance the pattern index; otherwise count it as a potential deletion. After processing the string, compute the number of removals required to isolate the matched subsequence. Since each pattern length is constant (2), the runtime stays linear in practice. This framing is useful when thinking about subsequences and enumeration strategies often seen in math or pattern‑matching problems.

Recommended for interviews: The greedy two-pointer approach is the expected solution. It directly uses the divisibility rule for 25 and achieves O(n) time with O(1) space. Showing the subsequence or DP interpretation demonstrates deeper reasoning, but interviewers typically want the greedy scan because it is simpler and more efficient.