Horje
Find smallest Substring to be rearranged to make String lexicographically sorted

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 code
int 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 code
s = "aabbace"
 
# // Function Call
print(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)


 


Reffered: https://www.geeksforgeeks.org

Strings

Related
Find the Longest Common Substring using Binary search and Rolling Hash Find the Longest Common Substring using Binary search and Rolling Hash
Pattern of Strings Pattern of Strings
Display the Longest Name Display the Longest Name
Minimum number of increment operations required to make two Strings equal Minimum number of increment operations required to make two Strings equal
Minimize String length by deleting Substring of same character when K flips are allowed Minimize String length by deleting Substring of same character when K flips are allowed

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje