You are given a 0-indexed string num representing a non-negative integer.
In one operation, you can pick any digit of num and delete it. Note that if you delete all the digits of num, num becomes 0.
Return the minimum number of operations required to make num special.
An integer x is considered special if it is divisible by 25.
Example 1:
Input: num = "2245047" Output: 2 Explanation: Delete digits num[5] and num[6]. The resulting number is "22450" which is special since it is divisible by 25. It can be shown that 2 is the minimum number of operations required to get a special number.
Example 2:
Input: num = "2908305" Output: 3 Explanation: Delete digits num[3], num[4], and num[6]. The resulting number is "2900" which is special since it is divisible by 25. It can be shown that 3 is the minimum number of operations required to get a special number.
Example 3:
Input: num = "10" Output: 1 Explanation: Delete digit num[0]. The resulting number is "0" which is special since it is divisible by 25. It can be shown that 1 is the minimum number of operations required to get a special number.
Constraints:
1 <= num.length <= 100num only consists of digits '0' through '9'.num does not contain any leading zeros.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.
In this approach, we work backwards on the string, aiming to find a pair at the end of the number that forms 00, 25, 50, or 75. These pairs are the multiples of 25. We start from the end of the string, looking to match these pairs and counting the deletions needed to make these the last two digits.
The function traverses the number string backwards and attempts to find a pair among the options '00', '25', '50', '75' that can be formed at the end of the string. For each target pair, the algorithm counts how many deletions (steps) are required to create the pair at the end of the number. A minimal count is constantly updated to ensure optimal deletions. The final count represents the minimum number of deletions required to make the number special.
Time Complexity: O(n) where n is the length of the input number string. We traverse the string a few times with a fixed amount of work for each character.
Space Complexity: O(1) as we only use a few extra variables for storage, ignoring input size.
This approach uses dynamic programming to explore every possible subsequence of the number, attempting to find at least one which has last two digits forming a multiple of 25. The observation is that which digits contribute to a valid subsequence can be stored in a DP table. We make a judgment based on these stored values about the minimal construction cost to create such subsequences.
This is a hypothetical placeholder, demonstrating that we consider the entire set of subsequences dimensional in a DP matrix or concept. The establishment of such a sequence matrix allows us to execute a greedy search within constrained size/variability under problem size constraints.
Due to being representative, suggested time complexity is O(n^2) with optimizations deriving from boundary conditions tested in earlier methods.
Space remains O(n^2).
We notice that an integer x can be divisible by 25, i.e., x bmod 25 = 0. Therefore, we can design a function dfs(i, k), which represents the minimum number of digits to be deleted to make the number a special number, starting from the ith digit of the string num, and the current number modulo 25 is k. The answer is dfs(0, 0).
The execution logic of the function dfs(i, k) is as follows:
i = n, i.e., all digits of the string num have been processed, then if k = 0, the current number can be divisible by 25, return 0, otherwise return n;ith digit can be deleted, in this case one digit needs to be deleted, i.e., dfs(i + 1, k) + 1; if the ith digit is not deleted, then the value of k becomes (k times 10 + num[i]) bmod 25, i.e., dfs(i + 1, (k times 10 + num[i]) bmod 25). Take the minimum of these two.To prevent repeated calculations, we can use memoization to optimize the time complexity.
The time complexity is O(n times 25), and the space complexity is O(n times 25). Here, n is the length of the string num.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Greedy using Two-Pointer Technique | Time Complexity: O(n) where n is the length of the input number string. We traverse the string a few times with a fixed amount of work for each character. |
| Approach 2: Dynamic Programming Subsequence Search | Due to being representative, suggested time complexity is O(n^2) with optimizations deriving from boundary conditions tested in earlier methods. |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Two-Pointer Search | O(n) | O(1) | Best general solution. Quickly finds valid endings (00, 25, 50, 75) with minimal deletions. |
| Dynamic Programming / Subsequence Matching | O(n * k) where k=4 patterns | O(k) | Useful when modeling the problem as subsequence matching or extending to more patterns. |
Leetcode Weekly contest 361 - Medium - Minimum Operations to Make a Special Number • Prakhar Agrawal • 2,574 views views
Watch 6 more video solutions →Practice Minimum Operations to Make a Special Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor