MYTH - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given a palindromic string of lowercase English letters, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible

QUICK EXPLANATION:

No solution is possible if the given string has a length of 1. If not replace the first character with a and if all the letters are a then replace the last character with b.

EXPLANATION:

A string of length 1 will always be palindrome irrespective of the character hence the answer for strings of length 1 will be mythistrue. If the length is not 1 we will try to replace a single character with a as we want to make the string lexicographically smallest moreover we will try to replace the character with a which is as left as possible again for the same reason to make string lexicographically smallest. If we failed to get a character that is not a then the string would be something like aaaaa.. in such a case we can replace the last character with b as its smallest after a and replacing the last character will give us the smallest string lexicographically.

One small optimization that we can do is instead of traversing the whole string from left to right we can only traverse the left or right half of the string as we know the string is a palindrome and hence both halves will be the same. Though the complexity will remain the same.

COMPLEXITIES

Here N is the size of S.

TIme Complexity:
O(N).
We are just traversing the array from left to right.

Space Complexity:
O(1)
We don’t need any extra space, we just need to traverse the string.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

string solve(string s) {

int i,start,end,n = s.size();

if(n==1)
	return "mythistrue";

start=0;end=n-1;

while(start<end)
{
	if(s[end]!='a')
	{
		s[start]='a';
		return s;
	}
	
	start++;
	end--;
}

s[n-1] = 'b';

return s;
}

int main() {
ios_base::sync_with_stdio(false);
int t;

cin>>t;

while(t--)
{
	string s;
	cin>>s;

	cout<<solve(s)<<endl;
}

return 0;
}
1 Like