ECAPR201 - Editorial

PROBLEM LINK:

Practice
April Encoding 2020

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))

Sorting the string and printing the first character also works, because the strings contain only alphabets

Submission link: https://www.codechef.com/viewsolution/33142666

yes but thats an O(nlogn) solution…the other methods I mentioned are faster…There also a O(26logn) solution where you loop over each alphabet and try to find them in the string using binary search. That’s probably the fastest solution that’s coming to my mind.

1 Like