Microsoft OA Lexicographically Smallest String

Microsoft Online Assessment 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.

Also See: Microsoft Online Assessment Questions and Solution

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.

Solution

Program Python:

def smallest_string(s: str) -> str:
    for i in range(len(s) - 1):

        if s[i] > s[i + 1]:
            break
    return s[:i] + s[i + 1:]
if __name__ == '__main__':
    s = input()
    res = smallest_string(s)
    print(res)

Program Java:

class Solution {
    public static String smallestString(String s) {
 
        int i = 0;

        for (; i < s.length() - 1; i++) {
            if (s.charAt(i) > s.charAt(i + 1)) {
                break;
            }
        }
        return s.substring(0, i) + s.substring(i + 1, s.length());
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();
        String res = smallestString(s);
        System.out.println(res);
    }
}


Program Javascript:

function smallestString(s) {

    let i = 0;

    for (; i < s.length - 1; i++) {
        if (s[i] > s[i + 1]) {
            break;
        }
    }
    return s.substr(0, i) + s.substr(i + 1, s.length);
}
function* main() {
    const s = yield;
    const res = smallestString(s);
    console.log(res);
}
class EOFError extends Error {}
{
    const gen = main();
    const next = (line) => gen.next(line).done && process.exit();
    let buf = '';
    next();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', (data) => {
        const lines = (buf + data).split('\n');
        buf = lines.pop();
        lines.forEach(next);
    });
    process.stdin.on('end', () => {
        buf && next(buf);
        gen.throw(new EOFError());
    });
}

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

Leave a Comment