PROBLEM LINK:
Author: arnie8991
Editorialist: arnie8991
DIFFICULTY:
Cake-Walk
PREREQUISITES:
Strings
EXPLANATION:
The problem asks us to find the lexicographically smallest palindrome in the string that consists of only lower case English characters. The shortest palindrome in a string is obviously a single character so our answer can be one of the 26 alphabets, the lower the alphabet, the better. So we scan the string for all the occurring characters and print the lexicographically lowest character. By lexicographically lowest, I mean that if there are 2 characters, ‘a’ and ‘b’, since ‘a’ comes before ‘b’ in the English alphabet, hence ‘a’ is lexicographically lower than ‘b’.
Time Complexity : O(N)
Space Complexity : O(26) or O(1)
SOLUTIONS No 1:
Setter Code #1
import java.util.*;
class Main{
public static void main(String args[]){
Scanner sc = new Scanner (System.in);
int[] arr = new int[26];
int n = sc.nextInt();
String s = sc.next();
for(char c: s.toCharArray()){
arr[c - 'a']++;
}
for(int i = 0; i < 26; i++){
if (arr[i] >= 1){
System.out.println((char)(i + 'a'));
return;
}
}
}
}
// Time complexity : O(N)
// Space Complexity: O(26)
SOLUTIONS No 2:
Setter’s Solution #2
import java.util.*;
class Main{
public static void main(String args[]){
Scanner sc = new Scanner (System.in);
int n = sc.nextInt();
String s = sc.next();
char lowest = s.charAt(0);
for(char c: s.toCharArray()){
if (c < lowest)
lowest = c;
}
System.out.println(lowest);
}
}
// Time complexity : O(N)
// Space Complexity: O(1)
Solution No 3
Tester’s Solution:
test = int(input())
for _ in range(test):
n = int(input())
s = list(input())
print(min(s))