Feature #5: Recover Files

Description#

A file contains a byte stream and some optional sections. These optional sections are identified by start and end delimiters. While downloading a file, some delimiters may get corrupted. This means that the starting delimiter may get replaced by an ending delimiter and vice versa. We cannot find which delimiter has been corrupted. Therefore, we need to remove the unmatched delimiters from the file to recover the file.

In this feature, we will make a tool to recover corrupted files by removing the minimum number of unmatched start or end delimiters.

Note: A file can contain nested delimiters.

We will be provided with a string that represents a file. Let’s look at a sample of this:

Let’s take a look at the edge cases:

Solution#

We will have to traverse the array to:

1. Check whether a delimiter is unmatched or not.
2. Note the index of the unmatched delimiter, so that we can remove it later on.

To do this, we will go over each character one by one. If the character is a delimiter, we will push it and its index in the stack. Otherwise, we will move on to the next character. To check whether the delimiter is matched or not, we will make the following check at each character: if the current character is an ending delimiter and the character at the top of the stack is a starting one, then both of them are matched. In such a case, we will not add the current character to the stack, and we will pop an element from the stack to remove the starting delimiter. This way, we will not have any matched delimiter in the stack.

Now, we will make a new string and start appending characters from the end of the original string in it. We are starting from the end because the positions of the unmatched delimiters are at the top of the stack. In the end, we will reverse the string and return it.

The following slideshow will clarify the process for us:

Let’s look at the code for the solution:

Complexity measures#

Time complexity#

The time complexity of this solution will be $O(n)$.

We will traverse the string only once to find any unmatched delimiters, and that will take $O(n)$ time.

Then, we will remove the unmatched delimiters from the string. In the worst-case scenario, all of the characters in the string can be unmatched delimiters—for example: )))(((. Hence, it would take $O(n)$ time.

When we combine the two, we will get $O(n) + O(n)$, which is equal to $O(n)$.

Space complexity#

In the worst-case scenario, all of the characters in the string can be unmatched delimiters—for example: )))(((. This will make the depth of the stack equal to the length of the string. So, the space complexity will be $O(n)$.