Microsoft OA 2023 Question Lexicographically Smallest String. We provide solution to Microsoft Online Assessment Questions and do check out our Microsoft OA 2023 Questions List below.
Contents
Lexicographically Smallest String Microsoft OA Solution
Lexicographically smallest string formed by removing at most one character.
Example 1:
Input: abczd
Output: abcd
Also See: Amazon OA Online Assessment 2023 Questions and Answers
SOLUTION
Program: Lexicographically Smallest String Solution in C++
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.
#include <iostream>
#include <vector>
using namespace std;
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;
}
int main() {
cout << "Result: " << solution("bba") << " Expected: ba" << endl;
cout << "Result: " << solution("abczd") << " Expected: abcd" << endl;
cout << "Result: " << solution("abcdz") << " Expected: abcd" << endl;
return 0;
}
Microsoft Online Assessment 2023 Questions List
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution