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 for i in range(len(s) - 1):
3 if s[i] > s[i + 1]:
4 break
5 return s[:i] + s[i + 1:]
6
7if __name__ == '__main__':
8 s = input()
9 res = smallest_string(s)
10 print(res)
11
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
1function smallestString(s) {
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.substr(0, i) + s.substr(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) => 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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.