Given a string str of length N. You have to choose a non-zero integer K (K <= N), such that in one operation you can take the prefix of the string of length K and append the reverse of it to itself, the task is to find the lexicographically smallest string you can get.
Examples:
Input: str = “bvdfndkn”
Output: bb
Explanation: If we choose K = 1, the prefix of length K will be “b”, and the reverse of this prefix will be “b” itself, when we append both we get “bb”, “bb” is the lexicographically smallest string you can get. If you choose K > 1, the resulting string will not be lexicographically smaller than “bb”.Input: str = “casd”
Output: caac
Explanation: Now here If we select K = 2, then the prefix of length K will be “ca”, the reverse of this prefix will be “ac”, when we append both we get “caac”, “caac” is the result.
Approach: To solve the problem follow the below idea:
- Construct the lexicographically smallest string by starting with the first character of s, and then iterating over the remaining characters.
- For each character s[i], check if it is smaller than the previous character s[i-1] or if it is equal to s[i-1] and s[i] is not equal to s[0].
- If either condition is true, append the character to the result string ans. If neither condition is true, break out of the loop.
- Once the result string ans is constructed, construct the reversed string by simply calling the reverse function on ans. Finally, return the concatenation of ans and rev to obtain the lexicographically smallest string.
Steps to solve the problem:
- Create an empty string called ans to store the lexicographically smallest string.
- Append the first character of the input string s to ans.
- Iterate over the remaining characters of s starting from the second character (index 1). For each character s[i], check if it is smaller than the previous character s[i-1] or if it is equal to s[i-1] and s[i]!=s[0].
- If either condition is true, append the character to ans. If neither condition is true, break out of the loop.
- Once the loop completes, construct the reversed string rev by calling the reverse function on ans.
- Finally, return the concatenation of ans and rev to obtain the lexicographically smallest string that can be obtained by performing the described operation.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;string stringMirror(string s){ string ans; ans.push_back(s[0]); for (int i = 1; i < s.size(); i++) { if (s[i] < s[i - 1] || (s[i] != s[0] && s[i] == s[i - 1])) ans.push_back(s[i]); else break; } string rev(ans); reverse(rev.begin(), rev.end()); return ans + rev;}// Drivers codeint main(){ string str1 = "bvdfndkn"; string str2 = "casd"; cout << "Input: " << str1 << endl; // Function Call cout << "Output: " << stringMirror(str1) << endl; cout << "Input: " << str2 << endl; // Function Call cout << "Output: " << stringMirror(str2) << endl; return 0;} |
Java
import java.util.*;public class Main { public static String stringMirror(String s) { StringBuilder ans = new StringBuilder(); ans.append(s.charAt(0)); for (int i = 1; i < s.length(); i++) { if (s.charAt(i) < s.charAt(i - 1) || (s.charAt(i) != s.charAt(0) && s.charAt(i) == s.charAt(i - 1))) { ans.append(s.charAt(i)); } else { break; } } StringBuilder rev = new StringBuilder(ans); rev.reverse(); return ans.toString() + rev.toString(); } public static void main(String[] args) { String str1 = "bvdfndkn"; String str2 = "casd"; System.out.println("Input: " + str1); System.out.println("Output: " + stringMirror(str1)); System.out.println("Input: " + str2); System.out.println("Output: " + stringMirror(str2)); }} |
Python3
def string_mirror(s): # Initialize the result with the first character of the string ans = [s[0]] # Iterate through the rest of the characters in the string for i in range(1, len(s)): # Check conditions for adding characters to the result if s[i] < s[i - 1] or (s[i] != s[0] and s[i] == s[i - 1]): ans.append(s[i]) else: # Break the loop if conditions are not met break # Create a reversed version of the result rev = ans[::-1] # Combine the result and its reverse to get the mirrored string return ''.join(ans + rev)# Driver codestr1 = "bvdfndkn"str2 = "casd"print("Input:", str1)# Function Callprint("Output:", string_mirror(str1))print("Input:", str2)# Function Callprint("Output:", string_mirror(str2)) |
C#
// C# code for the above approachusing System;public class GFG{ public static string StringMirror(string s) { string ans = ""; ans += s[0]; for (int i = 1; i < s.Length; i++) { if (s[i] < s[i - 1] || (s[i] != s[0] && s[i] == s[i - 1])) ans += s[i]; else break; } char[] rev = ans.ToCharArray(); Array.Reverse(rev); return ans + new string(rev); } // Drivers code public static void Main() { string str1 = "bvdfndkn"; string str2 = "casd"; Console.WriteLine("Input: " + str1); // Function Call Console.WriteLine("Output: " + StringMirror(str1)); Console.WriteLine("Input: " + str2); // Function Call Console.WriteLine("Output: " + StringMirror(str2)); }} |
Javascript
// JavaScript code for the above approachfunction stringMirror(s) { let ans = s[0]; for (let i = 1; i < s.length; i++) { if (s[i] < s[i - 1] || (s[i] !== s[0] && s[i] === s[i - 1])) { ans += s[i]; } else { break; } } let rev = ans.split('').reverse().join(''); return ans + rev;}// Driver codeconst str1 = "bvdfndkn";const str2 = "casd";console.log("Input: " + str1);// Function Callconsole.log("Output: " + stringMirror(str1));console.log("Input: " + str2);// Function Callconsole.log("Output: " + stringMirror(str2)); |
Output
Input: bvdfndkn Output: bb Input: casd Output: caac
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
