RemovingDigits
SRM 396 · 2008-04-03 · by asal1
SRM 396 · 2008-04-03 · by asal1 · Greedy, Search, String Manipulation
Problem Statement
Problem Statement
You are given two String s, number and digits. Each String contains only digits between 1 and 9, inclusive. For each occurrence of a digit in digits, you must remove a single occurrence of that digit from number. Your goal is to end up with the largest possible remaining number after all the necessary digits are removed. Return this number as a String .
Constraints
- number will contain between 1 and 50 characters, inclusive.
- digits will contain between 0 and n-1 characters, inclusive, where n is the number of characters in number.
- Each character in number and digits will be a non-zero digit ('1'-'9').
- The number of occurrences of each digit in number will be greater than or equal to the number of occurrences of that digit in digits.
Examples
0)
"12345" "513" Returns: "24"
If we remove the digits '5', '3', '1' we get the number 24.
1)
"112352" "1123" Returns: "52"
There are two choices. We can either get a "25" or a "52". The largest is "52".
2)
"123456654321" "612534" Returns: "654321"
Removing the first half of our number gives us the maximum result.
3)
"654321123456" "612534" Returns: "654321"
Removing the last half of our number gives us the maximum result.
4)
"2654982765982365" "2345978" Returns: "698265265"
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RemovingDigits with a public method string maxNumber(string number, string digits) · 88 test cases · 2 s / 256 MB per case