Best solutions for Microsoft interview tasks. Lexicographically Smallest String.

Description:

Lexicographically smallest string formed by removing at most one character.

Example 1:

Input: "abczd"
Output: "abcd"

Solution:

By definition of lexicographical order each next string is larger than the previous one А < АА < ААА < АAB < ААC < АB < B < … < ZZZ

Since we could only remove one character, we should remove the first char we meet that is greater than the next from left to right. In this case our string will be lexicographically smallest.

May be it looks more clear on numbers. Let us have a number 1324, we should remove 3 in order to make it smallest. Or let us have a number 389575, it is obvious we should remove 9 to make it smallest.

C++ code:

string solution(const string &s) {
    int i = 0, s_size = s.size();
    string result(s);
    for (; i < s_size - 1; ++i) {
        if (s[i] > s[i + 1]) {
            break;
        }
    }
    result.erase(i, 1);
    return result;
}

Repository with the full project you can find here: https://github.com/jolly-fellow/microsoft/tree/master/lexicographically_smallest_string

Return to the table of contents.