Given a string S, the task is to check if we can make the string lexicographically smaller by reversing any substring of the given string.
Examples:
Input: S = “striver”
Output: Yes
Reverse “rive” to get “stevirr” which is lexicographically smaller.
Input: S = “rxz”
Output: No
Approach: Iterate in the string and check if for any index s[i] > s[i + 1]. If there exists at least one such index, then it is possible else not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if s// can be made lexicographically smaller// by reversing a sub-string in sbool check(string &s){ int n = s.size(); // Traverse in the string for (int i = 0; i < n - 1; i++) { // Check if s[i+1] < s[i] if (s[i] > s[i + 1]) return true; } // Not possible return false;}// Driver codeint main(){ string s = "neveropen"; if (check(s)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach class GFG{// Function that returns true if s // can be made lexicographically smaller // by reversing a sub-string in s static boolean check(String s) { int n = s.length(); // Traverse in the string for (int i = 0; i < n - 1; i++) { // Check if s[i+1] < s[i] if (s.charAt(i) > s.charAt(i + 1)) return true; } // Not possible return false; } // Driver code public static void main(String args[]){ String s = "neveropen"; if (check(s)) System.out.println("Yes"); else System.out.println("No"); } }// This code is contributed by Arnab Kundu |
Python3
# Python 3 implementation of the approach# Function that returns true if s# can be made lexicographically smaller# by reversing a sub-string in sdef check(s): n = len(s) # Traverse in the string for i in range(n-1): # Check if s[i+1] < s[i] if (s[i] > s[i + 1]): return True # Not possible return False# Driver codeif __name__ == '__main__': s = "neveropen" if (check(s)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{// Function that returns true if s // can be made lexicographically smaller // by reversing a sub-string in s static bool check(String s) { int n = s.Length; // Traverse in the string for (int i = 0; i < n - 1; i++) { // Check if s[i+1] < s[i] if (s[i] > s[i + 1]) return true; } // Not possible return false; } // Driver code public static void Main(String []args){ String s = "neveropen"; if (check(s)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }// This code has been contributed by 29AjayKumar |
PHP
<?php// PHP implementation of the approach// Function that returns true if s// can be made lexicographically smaller// by reversing a sub-string in sfunction check($s){ $n = strlen($s); // Traverse in the string for ($i = 0; $i < $n - 1; $i++) { // Check if $s[$i+1] < $s[$i] if ($s[$i] > $s[$i + 1]) return true; } // Not possible return false;} // Driver code $s = "neveropen"; if (check($s)) echo "Yes"; else echo "No";// This code is contributed by jit_t?> |
Javascript
<script> // Javascript implementation of the approach // Function that returns true if s // can be made lexicographically smaller // by reversing a sub-string in s function check(s) { let n = s.length; // Traverse in the string for (let i = 0; i < n - 1; i++) { // Check if s[i+1] < s[i] if (s[i] > s[i + 1]) return true; } // Not possible return false; } let s = "neveropen"; if (check(s)) document.write("Yes"); else document.write("No"); </script> |
Output:
Yes
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), as constant extra space is required.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
