2264. Largest 3-Same-Digit Number in String
Problem Description
In this problem, we are provided with a string num that represents a large integer. We need to determine if there exists a 'good' integer within this string. A 'good' integer is defined by two specific criteria:
- It must be a substring of
numwith exactly a length of 3 characters. - All three characters of this substring must be the same digit, meaning it consists of only one unique digit.
The task is to return the largest such 'good' integer in string format. If no such 'good' integer exists, we are required to return an empty string "".
A 'substring' is defined as a continuous sequence of characters within the string. It's also important to note that 'good' integers can contain leading zeroes, as they are part of the string num.
The problem is essentially asking us to look for triplets within the string where all three characters are the same and return the highest numerical value triplet. For example, if single-digit triplets '222', '555', and '777' are all found in num, then we should return '777' as it represents the largest good integer.
Intuition
The solution employs a straightforward approach. Since we are asked for the largest good integer, we can employ a strategy where we start looking for triplets from the largest digit (9) and work our way down to the smallest digit (0).
The key insights that lead us to this solution are:
- Given that we're looking for sequences of the same digit, we know that '999' is the largest possible good integer and '000' is the smallest.
- The problem statement defines that a good integer has a fixed length of 3. Hence, we don't need to consider substrings of any other length.
- If a larger triplet is found, we don't need to continue searching since we are guaranteed that no larger good integer can exist.
- Due to the ordering of digits (9 to 0), the first matching triplet we come across will be the largest one, and we can terminate the search immediately and return the result.
Taking these points into consideration, the algorithm iterates over digits from 9 to 0 and checks if a substring of three similar digits exists in num. As soon as such a substring is found, the algorithm stops and we return the substring. If no such triplet is found after checking all digits, we conclude that no good integer is present, and we return an empty string.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Solution Approach
The solution approach utilizes a simple but effective strategy which is a countdown loop that checks for the presence of triplets of the same digit within the input string num. The approach is essentially a search problem with a greedy method for finding the maximum good integer by checking the highest possible digits first.
Algorithm:
We iterate over the possible digits in descending order, starting from 9, since we want to find the maximum good integer. This is a greedy choice since we aim to return the largest possible triplet of digits.
For each digit i in the range from 9 down to 0, we do the following:
- We create a string
sthat consists of three identical characters of the digiti. This is achieved by multiplying the string representation ofiby 3 (i.e.,s = str(i) * 3). - Check if the string
sis a substring ofnum. To do this, we use theinkeyword in Python which checks for substring existence. - If
sis found withinnum, we immediately returnsas we have located the largest possible good integer up to that point. - If no match is found after checking all digits down to 0, the function returns an empty string, indicating no good integer exists in
num.
Data Structures:
No additional data structures are used in this approach since we are directly checking substrings within the given string and there is no need for auxiliary storage.
Patterns:
This approach uses a greedy algorithm pattern, where the solution builds the optimum choice step by step. In this case, the optimal choice at each step is the largest digit that forms a good integer. By starting from 9 and working downwards, we ensure that the first matching substring is also the largest possible one.
Here is the code block which represents our solution approach:
1class Solution:
2 def largestGoodInteger(self, num: str) -> str:
3 for i in range(9, -1, -1): # Loop over digits from 9 to 0
4 if (s := str(i) * 3) in num: # Check if the triplet is in num
5 return s # Return the largest good integer found
6 return "" # Return an empty string if no good integer exists
The simplicity of this solution lies in the fact that it combines enumeration with a greedy strategy to minimize the number of checks required. It doesn't require complex algorithms or data structures, making it both easy to understand and efficient to execute.
Which of the following is a good use case for backtracking?
Example Walkthrough
Let's consider the input string num = "4233312221555". We are tasked with finding the largest 'good' integer. A 'good' integer is a triplet of the same digit.
Step 1: We begin by checking for the triplet '999'. Since '999' does not appear in our input string, we move on to the next digit.
Step 2: We then check for the triplet '888'. This triplet also does not appear in our input string.
Step 3: We continue this process with '777', '666', and '555'. When we check for '555', we find that it does exist in the input string '4233312221555'.
Step 4: We return '555' immediately since it is the largest 'good' integer that can be found by our search and we do not need to check for triplets of any smaller digit. There is no need to search for '444', '333', '222', or '111', let alone '000', because we are guaranteed they won't give us a larger 'good' integer than what we've already found ('555').
Therefore, using our solution approach, for the input num = "4233312221555", the largest good integer is '555'.
Solution Implementation
1class Solution:
2 def largestGoodInteger(self, num: str) -> str:
3 # Iterate over the digits in descending order, starting from 9 to 0.
4 for digit in range(9, -1, -1):
5 # Create a string of three consecutive identical digits.
6 triple_digit_str = str(digit) * 3
7
8 # Check if this string of three identical digits is in the input 'num'.
9 if triple_digit_str in num:
10 # If found, return this largest 'good' integer as the result.
11 return triple_digit_str
12
13 # If no such triple is found in the number, return an empty string.
14 return ""
151class Solution {
2 // Method to find the largest good integer in the given string.
3 public String largestGoodInteger(String num) {
4 // Loop backwards from '9' to '0'
5 // This will ensure that the first good integer found is the largest
6 for (int i = 9; i >= 0; i--) {
7 // Create a string consisting of three identical digits
8 String tripleDigit = String.valueOf(i).repeat(3);
9
10 // Check if the num string contains the tripleDigit
11 if (num.contains(tripleDigit)) {
12 // Return the found good integer (since we started from 9, it's the largest)
13 return tripleDigit;
14 }
15 }
16 // If no good integer is found, return an empty string
17 return "";
18 }
19}
201class Solution {
2public:
3 // Function to find the largest 3-digit substring with identical digits
4 string largestGoodInteger(string num) {
5 // Start checking from '9' down to '0' to find max "good" integer snippet
6 for (char digit = '9'; digit >= '0'; --digit) {
7 // Create a string consisting of three identical characters (digits)
8 string triplet(3, digit);
9
10 // If the triplet is found in 'num', return it as it's the largest "good" integer
11 if (num.find(triplet) != string::npos) {
12 // Return the first instance of the largest "good" integer found
13 return triplet;
14 }
15 }
16 // If no triplet found, return an empty string
17 return "";
18 }
19};
201// This function finds the largest "good integer" in the given number string.
2// A "good integer" is a substring that consists of three identical consecutive digits.
3function largestGoodInteger(num: string): string {
4 // Iterate from the largest possible digit (9) to the smallest (0).
5 for (let currentDigit = 9; currentDigit >= 0; currentDigit--) {
6 // Create a string with the current digit repeated three times.
7 const tripleDigit = String(currentDigit).repeat(3);
8 // Check if the current triple digit string exists in the input number string.
9 if (num.includes(tripleDigit)) {
10 // If found, return the current triple digit string as it is the largest "good integer" found so far.
11 return tripleDigit;
12 }
13 }
14 // If no "good integer" is found, return an empty string.
15 return '';
16}
17Which data structure is used to implement priority queue?
Time and Space Complexity
The given Python code snippet defines a function largestGoodInteger that searches for the largest 3-digit same numeric substring within a given string num. The function loops decrementally from 9 to 0, constructs a string s of three identical digits, and checks whether this string is contained within the input num.
Time Complexity
The time complexity of the provided code can be analyzed as follows:
- The
forloop runs from9to0, which is10iterations. - Within each iteration, the
inoperator is used to check for the presence of a 3-digit substringswithin the stringnum. Theinoperator, in the worst case, has to check each character innumagainsts, leading to anO(n)operation for each check, wherenis the length ofnum. - Since we perform this check for
10potential substrates (999,888, ...,000), the overall time complexity isO(10 * n).
Thus, the time complexity is indeed O(10 * n) as mentioned in the reference answer.
Space Complexity
For space complexity, we consider the following:
- The variable
sis created within the loop, consisting of a 3-character string. This space is reused and does not depend on the input size. - No additional data structures or dynamic memory allocations are used that grow with the size of the input.
- The input
numand the constant 3-character stringsdo not count towards additional space since the space complexity analysis accounts for only the extra space required by the algorithm beyond the input.
Therefore, the space complexity is O(1), which means that the amount of memory required does not change with the size of the input string num.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.