Microsoft Online Assessment (OA) - Lexicographically Smallest String

Given a string str, the task is to find the lexicographically smallest string that can be formed by removing at most one character from the given string.

Example 1:

Input: `abczd`

Output: `abcd`

Example 2:

Input: `abcda`

Output: `abca`

Explanation:

One can remove d to get abca, which is the lexicographically smallest string possible.

Try it yourself

Implementation

1def smallest_string(s: str) -> str:
2    i = 0
3    for i in range(len(s) - 1):
4        if s[i] > s[i + 1]:
5            break
6    return s[:i] + s[i + 1 :]
7
8if __name__ == "__main__":
9    s = input()
10    res = smallest_string(s)
11    print(res)
12

1import java.util.Scanner;
2
3class Solution {
4    public static String smallestString(String s) {
5        int i = 0;
6        for (; i < s.length() - 1; i++) {
7            if (s.charAt(i) > s.charAt(i + 1)) {
8                break;
9            }
10        }
11        return s.substring(0, i) + s.substring(i + 1, s.length());
12    }
13
14    public static void main(String[] args) {
15        Scanner scanner = new Scanner(System.in);
16        String s = scanner.nextLine();
17        scanner.close();
18        String res = smallestString(s);
19        System.out.println(res);
20    }
21}
22

1"use strict";
2
3function smallestString(s) {
4    let i = 0;
5    for (; i < s.length - 1; i++) {
6        if (s[i] > s[i + 1]) {
7            break;
8        }
9    }
10    return s.substr(0, i) + s.substr(i + 1, s.length);
11}
12
13function* main() {
14    const s = yield;
15    const res = smallestString(s);
16    console.log(res);
17}
18
19class EOFError extends Error {}
20{
21    const gen = main();
22    const next = (line) => gen.next(line).done && process.exit();
23    let buf = "";
24    next();
25    process.stdin.setEncoding("utf8");
26    process.stdin.on("data", (data) => {
27        const lines = (buf + data).split("\n");
28        buf = lines.pop();
29        lines.forEach(next);
30    });
31    process.stdin.on("end", () => {
32        buf && next(buf);
33        gen.throw(new EOFError());
34    });
35}
36

1function smallestString(s: string): string {
2    let i = 0;
3    for (; i < s.length - 1; i++) {
4        if (s[i] > s[i + 1]) {
5            break;
6        }
7    }
8    return s.substring(0, i) + s.substring(i + 1, s.length);
9}
10
11function* main() {
12    const s = yield;
13    const res = smallestString(s);
14    console.log(res);
15}
16
17class EOFError extends Error {}
18{
19    const gen = main();
20    const next = (line?: string) => gen.next(line ?? "").done && process.exit();
21    let buf = "";
22    next();
23    process.stdin.setEncoding("utf8");
24    process.stdin.on("data", (data) => {
25        const lines = (buf + data).split("\n");
26        buf = lines.pop() ?? "";
27        lines.forEach(next);
28    });
29    process.stdin.on("end", () => {
30        buf && next(buf);
31        gen.throw(new EOFError());
32    });
33}
34