Several possible approaches to this problem are provided below, along with their complexity information.
In this challenge, you needed to compare adjacent characters to determine whether they are the same letter, but differently cased. There are two general approaches for doing this. In the solutions given in this lesson, either approach can be substituted for the other.
The first approach uses Ruby methods; either upcase
or downcase
can be used:
# Ruby upcase (or downcase) method:
str[i] != str[i + 1] && str[i].upcase == str[i + 1].upcase
The second approach uses ASCII math, along with the Ruby #ord
method, which
returns the numeric ASCII value of a character. See the ASCII
table for more info.
# ASCII math
(str[i].ord - str[i + 1].ord).abs != 32
In this solution, we're using the stack to hold characters that aren't "bad". We iterate through the string and, for each character, compare it the top element in the stack. If the comparison is "good", we add the character to the stack; otherwise, we pop the top element off the stack and continue. In this way, we can compare characters that are newly adjacent (i.e., one or more pairs of "bad" characters between them have been removed) without iterating through the string multiple times.
After the iteration is finished, we pop each element off the stack in turn, add it to our result string, and return that value.
def fix_the_string(str)
# we can use an array to stand in for a stack, or implement a stack class
stack = []
# Iterate through the string, adding the "good" characters to the stack
str.each_char do |char|
if !stack.empty? && char != stack.last && char.upcase == stack.last.upcase
stack.pop
else
stack.push(char)
end
end
# Pop each element off the stack and add it to the result string
result = ''
result = stack.pop + result until stack.empty?
result
end
Time: O(n)
Space: O(n)
Time: The time complexity for both iterating through the string and popping elements off the stack is O(n), giving us O(2n), which simplifies to O(n).
Space: We create a stack variable to hold the "good" characters and a string variable to hold the result. In the worst case — no "bad" characters found — they will both wind up holding all of the characters. This gives a complexity of O(n) for each or O(2n) total, which reduces to O(n).
This solution and the ones that follow use what is called an "in-place" solution. In other words, the input string is manipulated as you go through the iteration.
Here we use the outer while
loop to keep iterating as long as changes are
being made to the string. The inner loop iterates through the characters of the
string, identifies adjacent characters to be removed, and updates the string. It
also resets continue
to true
so the while loop will continue. The break
breaks out of the inner loop so we're back in the outer loop, which then
restarts the inner loop with the new value of str
.
Once str
contains no adjacent "bad" characters, the code inside the if
statement will not execute and the while
loop will end.
def fix_the_string(str)
continue = true
while continue
continue = false
(str.size - 1).times do |i|
# If a pair of "bad" characters is found, remove them from the string,
# update the boolean to continue the outer loop, and end the inner loop
if (str[i] != str[i + 1]) && (str[i].upcase == str[i + 1].upcase)
str = str[0...i] + str[i + 2..-1]
continue = true
break
end
end
end
str
end
- Time: see below
- Space : O(1)
Time: Given that this solution uses nested loops, you might expect the time complexity to be O(n²). However, because the string is being modified "in place", the actual number of steps required would never reach n². For our purposes, it is enough to know that the time complexity will fall somewhere between O(n) and O(n²). However, for those who are interested, there is a more complete discussion at the bottom of the page.
Space: The only extra variable we are using here is i
, which does not grow
with the size of the input. Therefore, the space complexity is O(1).
This solution is basically the same as the one above, but instead of explicitly
using a second loop, it manipulates the value of the counter variable, i
. The
end result is the same in terms of complexity.
If a pair of characters is removed, i
is reset to 0
so that, in the next
iteration of the loop, the string is checked from the beginning again. This
ensures that newly adjacent "bad" characters are found. Otherwise, i
is
incremented and the loop continues.
The loop ends if either i
reaches the end of the string or if all the
characters have been removed from the string.
def fix_the_string(str)
i = 0
while i < str.size - 1 && !str.empty?
if bad_pair?(str[i], str[i + 1])
str.slice!(i..i + 1)
i = 0
else
i += 1
end
end
str
end
Although this solution doesn't explicitly use nested loops, the changes to i
have the same effect. Therefore, the complexity for this example is the same as
for sample #2.
This solution uses a "two-pointer" approach. The first pointer (i
) is simply
used to iterate through the input string. Modifications are made to the string
as we go, "behind" i
, to overwrite "bad" characters.
The second pointer, j
, keeps track of where we are in the modified version of
the string, i.e., the location where the last "good" character is. j
is only
advanced if we know the current character is good, and "bad" characters are
overwritten at the location of j
. This ensures that everything up to j
is
good and should be returned at the end of the method.
Note that we aren't removing characters as we go, so the string will still be
its original length by the end of the method. We use j
to return just the
portion of the string we know is good.
def fix_the_string(str)
j = 0
i = 0
while i < str.size
# If we find a pair that needs to be removed, we want to "back up" j and not include
# the current character in the modified version of the string
if j > 0 && (str[i].ord - str[j - 1].ord).abs == 32
j -= 1
else
# otherwise, we set the character at j to the "good" character at the current value of i
str[j] = str[i]
j += 1
end
i += 1
end
# We return the portion of the string up to j - 1, the location of the last "good" character
str[0..j - 1]
end
Time: O(n)
Space: O(1)
Time: We just have a single iteration through the string, which gives complexity of O(n)
Space: The only extra variables we are using here are i
and j
, which do not
grow with the size of the input. Therefore, the space complexity is O(1).
The outer loop will only execute once if the string is already good. If there are "bad" pairs, it will execute one additional time for each pair found. Therefore, in the worst case, the number of times the outer loop will run is n/2 + 1, since a string of length n can only have n/2 matching pairs.
For example, given the string aAbBcCdDeE
, the loop will execute 6 times. (In
the last iteration, all that will happen is the boolean value will be updated to
end the loop).
Within each outer loop, the inner loop will execute until the first "bad" pair is found. Once that happens, the inner loop is "short-circuited". If the first "bad" pair is at the front of the string, it will only execute once in that iteration of the outer loop.
For example, given the same string, aAbBcCdDeE
, the inner loop will execute
once for each iteration through the outer loop except the last one, for a total
of 5. However, if we were to rearrange the string so the matched pairs occur
from the middle out — abcdeEDCBA
— the inner loop has to execute more times to
find each of the bad pairs.
The total number of steps, therefore, depends on a combination of three factors: the number of matched pairs the string contains, the number of unmatched characters it contains, and how the matched pairs are arranged within the string.
We can be sure that the complexity will fall somewhere between O(n) and O(n²), but we can actually do a bit better than that. Because the outer loop executes a maximum of n/2 times, and the inner loop is short-circuited by the in-place changes to the string, the change to the total number of steps relative to the size of the input string will be much closer to n than to n².
Test it out for yourself: you can add a counter variable inside the inner loop and see how changes to the input string affect the number of steps.