Given a string S, the task is to find out the length of the smallest substring of S that needs to be rearranged so that all the characters of the string S are in lexicographical order.
Examples:
Input: S = “aabbace”
Output: 3
Explanation: Rearranging “bba” to be “abb”.
S becomes “aaabbce” which is in lexicographical order.Input: S = “abez”
Output: 0
Approach: Follow the steps to solve the problem:
- Compare each character S[i] from 0 to N-2 with all it’s succeeding characters.
- Once we find a lexicographically smaller character than the previous one,
- We store the index of the last character in end if it’s index position is maximum and
- The preceding character in start if it’s index position is minimum and
- Also update ans which is our required string length that needs to be modified.
- Add 1 to the difference of end and start because it is 0-indexed.
- If the string is already arranged in lexicographical order, return 0.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int smallestsubstring(string s){ int n = s.size(), ans = 0, start = INT_MAX, end = INT_MIN; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) if ((int)s[j] < (int)s[i]) { start = min(start, i); end = max(end, j); ans = end - start + 1; } } return ans;}// Drivers codeint main(){ string s = "aabbace"; // Function Call cout << smallestsubstring(s); return 0;} |
Java
// JAVA code for the above approach:import java.util.*;class GFG { static int smallestsubstring(String s) { int n = s.length(), ans = 0, start = Integer.MAX_VALUE, end = Integer.MIN_VALUE; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) if ((int)s.charAt(j) < (int)s.charAt(i)) { start = Math.min(start, i); end = Math.max(end, j); ans = end - start + 1; } } return ans; } // Drivers code public static void main(String[] args) { String s = "aabbace"; // Function Call System.out.println(smallestsubstring(s)); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach:def smallestsubstring(s): n = len(s) ans = 0 start = 2147483647 end = -2147483647 - 1 for i in range(0,n-1): for j in range(i+1,n): if (s[j] < s[i]): start = min(start, i) end = max(end, j) ans = end - start + 1 return ans# Drivers codes = "aabbace"# // Function Callprint(smallestsubstring(s))# This code is contributed by ksam24000 |
C#
// C# code for the above approach:using System;public class GFG { static int smallestsubstring(String s) { int n = s.Length, ans = 0, start = Int32.MaxValue, end = Int32.MinValue; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) if ((int)s[j] < (int)s[i]) { start = Math.Min(start, i); end = Math.Max(end, j); ans = end - start + 1; } } return ans; } // Drivers code static public void Main() { String s = "aabbace"; // Function Call Console.WriteLine(smallestsubstring(s)); }}// This code is contributed by Rohit Pradhan |
Javascript
<script> // JavaScript code for the above approach function smallestsubstring(s) { let n = s.length, ans = 0, start = Number.MAX_VALUE; end = Number.MIN_VALUE for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) if (s[j] < s[i]) { start = Math.min(start, i); end = Math.max(end, j); ans = end - start + 1; } } return ans; } // Driver Function let s = "aabbace"; // Function Call document.write(smallestsubstring(s)); // This code is contributed by sanjoy_62.</script> |
Output
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
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!
Share your thoughts in the comments
