1957. Delete Characters to Make Fancy String
Problem Description
In this problem, we are dealing with the concept of a "fancy string". A string is considered fancy if no three consecutive characters are identical. The goal is to transform any given string s
into a fancy string by removing the minimum number of characters necessary.
For example, if the input string is s = "aaabaaaa"
, a possible fancy string could be s = "aabaa"
after deleting the right characters. The task is to return the modified string that fulfills the condition of being a fancy string.
Intuition
To approach this problem, we need to scan through the input string and check for any occurrence of three identical consecutive characters. Whenever we find such a sequence, we don't include the third character in our result.
A straightforward way to do this is to iterate over each character in the input string while maintaining a separate list to build the fancy string. For each character, we compare it with the last two characters in the list. If all three are the same, we skip adding the current character to the list; otherwise, we add it.
This process ensures that at no point will there be three identical consecutive characters in our resultant list. In the end, we join the characters in the list to form the final fancy string and return it. This solution has the advantage of examining each character only once, giving us a time-efficient approach to making the string fancy.
Solution Approach
The solution to the problem makes use of a simple iteration pattern over the characters of the string, coupled with a condition check to enforce the "fancy" constraint.
To implement this, we use a Python list, ans
, which is a dynamic array in this context. We iterate through each character c
in the input string s
, and check if this character is about to form a triplet with the two previously added characters (if any).
Here's a step-by-step breakdown of the solution:
-
Initialization: An empty list
ans
is created which will store the characters that will eventually make up the fancy string. -
Iteration: We iterate over each character
c
in the given strings
. -
Condition Check: Before adding the character
c
to the listans
, we perform a check:- If the length of
ans
is greater than 1 (which means there are at least two characters already inans
), - And the last character (
ans[-1]
) and the second to last character (ans[-2]
) inans
are both equal toc
, - Then this character
c
would create a sequence of three identical consecutive characters. In this case, we simply skip addingc
toans
.
- If the length of
-
Character Addition: If the check fails (meaning adding
c
won't lead to three consecutive identical characters), we addc
to the listans
. -
Result Formation: Once we've finished iterating over the string, we use
''.join(ans)
to concatenate all the elements in the listans
into a string, which is the fancy string that we return as the result.
By using a for loop and a conditional statement, we are able to enforce the consecutive character constraint efficiently. The usage of an array (list
in Python) to build our result allows for easy appending and checking of the last two characters. This approach has a linear runtime complexity because each character in the input string is processed exactly once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a smaller example to illustrate the solution approach using the input string s = "xxxyyyz"
. Following the solution approach step by step, we will transform s
into a fancy string.
-
Initialization: We create an empty list
ans
which will collect the characters for the fancy string. -
Iteration:
- We begin by iterating over each character in
s
. The first character is'x'
.
- We begin by iterating over each character in
-
Condition Check:
- Since
ans
is empty, we do not need to check for triplets. There are no previous characters to compare with.
- Since
-
Character Addition:
- We add
'x'
toans
, resulting inans = ['x']
.
- We add
-
Next Iteration:
- The next character is
'x'
. We checkans
and find there is only one'x'
, so we can safely add another. ans = ['x', 'x']
.
- The next character is
-
Next Iteration:
- We encounter
'x'
again. We check the last two characters ofans
and find that adding another'x'
would create three in a row, which is not allowed for a fancy string. - We skip adding this
'x'
and move on to the next character.
- We encounter
-
Next Iteration:
- The next character is
'y'
. There's no issue in adding'y'
toans
as it wouldn't create three identical consecutive characters. ans = ['x', 'x', 'y']
.
- The next character is
-
Continued Iteration:
- We continue this process for the remaining characters
'y'
,'y'
, and'z'
. For both occurrences of'y'
after the first, we skip adding them since they would create a triplet with the previous two'y's
. Finally,'z'
can be added without any problems. ans = ['x', 'x', 'y', 'z']
.
- We continue this process for the remaining characters
-
Result Formation:
- At the end of the iteration, we join the characters in
ans
to form the final string. - The fancy string is
'xxyz'
.
- At the end of the iteration, we join the characters in
In this example, by following the solution approach, we removed two characters 'y'
and one character 'x'
to transform "xxxyyyz"
into a fancy string "xxyz"
. This process minimizes the number of deletions needed and ensures that no three consecutive characters in the result are identical.
Solution Implementation
1class Solution:
2 def makeFancyString(self, s: str) -> str:
3 # Initialize an empty list to store the modified characters of the string
4 result = []
5
6 # Iterate over each character in the input string
7 for char in s:
8 # Check if the last two characters in 'result' are the same as the current character
9 if len(result) > 1 and result[-1] == result[-2] == char:
10 # If true, skip adding the current character to avoid three consecutive identical characters
11 continue
12 # Otherwise, append the current character to the result list
13 result.append(char)
14
15 # Join all characters in the result list to form the modified string
16 return ''.join(result)
17
1class Solution {
2 // Method to transform the input string into a fancy string
3 // A fancy string is a string where no three consecutive characters are equal
4 public String makeFancyString(String s) {
5 // StringBuilder is initialized to build the fancy string efficiently
6 StringBuilder fancyString = new StringBuilder();
7
8 // Iterate over each character in the input string
9 for (char currentChar : s.toCharArray()) {
10 // Calculate the length of the current fancyString
11 int currentLength = fancyString.length();
12
13 // Check if the last two characters in fancyString are the same as the current character
14 if (currentLength > 1 &&
15 fancyString.charAt(currentLength - 1) == currentChar &&
16 fancyString.charAt(currentLength - 2) == currentChar) {
17 // If true, continue to the next iteration to avoid adding a third consecutive character
18 continue;
19 }
20
21 // Append the current character to fancyString
22 fancyString.append(currentChar);
23 }
24
25 // Convert the StringBuilder to a String and return it
26 return fancyString.toString();
27 }
28}
29
1class Solution {
2public:
3 // Method that converts a string into a 'fancy string'.
4 // A 'fancy string' is a string where no three consecutive characters are equal.
5 string makeFancyString(string s) {
6 string result; // Initialize an empty string to store the 'fancy string'.
7
8 // Iterate through each character in the input string.
9 for (char& currentChar : s) {
10 int currentLength = result.size(); // Get the current length of the 'fancy string'.
11
12 // Check if the last two characters in the 'fancy string' are the same as the current character.
13 if (currentLength > 1 && result[currentLength - 1] == currentChar && result[currentLength - 2] == currentChar) {
14 // If the last two characters are the same as the current character, skip adding this character.
15 continue;
16 }
17
18 // Append the current character to the 'fancy string' if no three consecutive characters are the same.
19 result.push_back(currentChar);
20 }
21
22 // Return the 'fancy string'.
23 return result;
24 }
25};
26
1// Function that converts a string into a 'fancy string'.
2// A 'fancy string' is a string where no three consecutive characters are equal.
3function makeFancyString(s: string): string {
4 let result = ''; // Initialize an empty string to store the 'fancy string'.
5
6 // Iterate through each character in the input string.
7 for (let i = 0; i < s.length; i++) {
8 const currentChar = s[i]; // Get the current character.
9 const currentLength = result.length; // Get the current length of the 'fancy string'.
10
11 // Check if the last two characters in the 'fancy string' are the same as the current character.
12 if (currentLength > 1 && result[currentLength - 1] === currentChar && result[currentLength - 2] === currentChar) {
13 // If the last two characters are the same as the current character, skip adding this character.
14 continue;
15 }
16
17 // Append the current character to the 'fancy string' if no three consecutive characters are the same.
18 result += currentChar;
19 }
20
21 // Return the 'fancy string'.
22 return result;
23}
24
25// Example usage:
26// const fancyString = makeFancyString("aaabccc");
27// console.log(fancyString); // Output should be "aabcc"
28
Time and Space Complexity
Time Complexity
The given code loops over each character in the input string s
only once. The condition inside the loop checks the last two characters in the ans
list to determine if the current character c
should be added to ans
.
Since each character in s
is processed once and each operation within the loop, including comparison and list appending, is O(1), the overall time complexity of the algorithm is O(n), where n
is the length of the input string s
.
Space Complexity
The space complexity of the code is mostly determined by the space used to store the ans
list. In the worst case, when no characters are the same, ans
will contain all the characters of s
. Therefore, the space complexity is O(n) as well, where n
is the length of the input string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!