Количество лексикографически меньших символов справа

Опубликовано: 1 Декабря, 2021

Дана строка, состоящая только из строчных букв английского алфавита. Задача состоит в том, чтобы подсчитать общее количество алфавитно меньших символов справа от символов по каждому индексу.

Примеры:

Input: str = “edcba”
Output: 4 3 2 1 0
Explanation:
The number of characters on the right side of index 0 which is smaller than
e are dcba = 4
The number of characters on the right side of index 1 which is smaller than
d are cba = 3
The number of characters on the right side of index 2 which is smaller than
c are ba = 2
The number of characters on the right side of index 3 which is smaller than
b are a = 1
The number of characters on the right side of index 4 which is smaller than
a are ‘’ = 0
Input: str = “eaaa”
Output: 3 0 0 0

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход:
Идея состоит в том, чтобы обойти все символы с правой стороны каждого индекса строки один за другим и вывести количество символов, которые в алфавитном порядке меньше.

Сложность времени: O ( N ² ), где N = длина строки
Вспомогательное пространство: O (1)

Лучший подход: идея состоит в том, чтобы использовать самобалансирующийся BST.
Самобалансирующееся двоичное дерево поиска (AVL, Red Black и т. Д.) Может использоваться для получения решения с временной сложностью O (N log N). Мы можем дополнить эти деревья так, чтобы каждый узел N содержал размер поддерева с корнем N. Мы использовали дерево AVL в следующей реализации.
Мы обходим строку справа налево и вставляем все элементы один за другим в дерево AVL. Вставляя новый ключ в дерево AVL, мы сначала сравниваем ключ с корнем. Если ключ больше корня, то он больше всех узлов в левом поддереве корня. Итак, мы добавляем размер левого поддерева к количеству более мелких элементов для вставляемого ключа. Мы рекурсивно следуем одному и тому же подходу для всех узлов в корне.
Пожалуйста, обратитесь к этой статье для реализации описанного выше подхода.
Сложность времени: O ( N * log N )
Вспомогательное пространство: O ( N )

Эффективный подход:
Идея состоит в том, чтобы использовать методы хеширования, потому что строка состоит только из строчных букв. Итак, здесь мы можем взять массив размером 26, который используется для хранения количества меньших символов с правой стороны этого индекса.
Пройдите по массиву справа и продолжайте обновлять количество символов в хеш-массиве. Теперь, чтобы найти количество меньших символов справа, мы можем просто обходить хэш-массив размером 26 каждый раз, чтобы подсчитать меньшие символы, встреченные до сих пор.

C ++

 #include <bits/stdc++.h>
 using namespace std;
 // Function to count the smaller
 // characters on the right of index i
 void countSmaller(string str)
 {
    // store the length of string
    int n = str.length(); 
    // initialize each elements of
    // arr to zero
    int arr[26] = { 0 }; 
    // array to store count of smaller characters on
    // the right side of that index
    int ans[n]; 
    for ( int i = n - 1; i >= 0; i--) { 
        arr[str[i] - 'a' ]++; 
        // initialize the variable to store
        // the count of characters smaller
        // than that at index i
        int ct = 0; 
        // adding the count of characters
        // smaller than index i
        for ( int j = 0; j < str[i] - 'a' ; j++) {
            ct += arr[j];
        }
        ans[i] = ct;
    }
    // print the count of characters smaller
    // than index i stored in ans array
    for ( int i = 0; i < n; i++) {
        cout << ans[i] << " " ;
    }
 }
 // Driver Code
 int main()
 {
    string str = "edcbaa" ;
    countSmaller(str);
    return 0;
 }

Ява

 class GFG
 {
 // Function to count the smaller
 // characters on the right of index i
 static void countSmaller(String str)
 {
    // store the length of String
    int n = str.length(); 
    // initialize each elements of
    // arr to zero
    int arr[] = new int [ 26 ]; 
    // array to store count of smaller characters on
    // the right side of that index
    int ans[] = new int [n]; 
    for ( int i = n - 1 ; i >= 0 ; i--)
    {
        arr[str.charAt(i) - 'a' ]++; 
        // initialize the variable to store
        // the count of characters smaller
        // than that at index i
        int ct = 0 ; 
        // adding the count of characters
        // smaller than index i
        for ( int j = 0 ; j < str.charAt(i) - 'a' ; j++)
        {
            ct += arr[j];
        }
        ans[i] = ct;
    }
    // print the count of characters smaller
    // than index i stored in ans array
    for ( int i = 0 ; i < n; i++)
    {
        System.out.print(ans[i] + " " );
    }
 }
 // Driver Code
 public static void main(String[] args)
 {
    String str = "edcbaa" ;
    countSmaller(str);
 }
 }
 // This code is contributed by 29AjayKumar

Python3

 # Function to count the smaller
 # characters on the right of index i
 def countSmaller( str ): 
    # store the length of String
    n = len ( str ); 
    # initialize each elements of
    # arr to zero
    arr = [ 0 ] * 26 ; 
    # array to store count of smaller characters on
    # the right side of that index
    ans = [ 0 ] * n; 
    for i in range (n - 1 , - 1 , - 1 ): 
        arr[ ord ( str [i] ) - ord ( 'a' )] + = 1 ; 
        # initialize the variable to store
        # the count of characters smaller
        # than that at index i
        ct = 0 ; 
        # adding the count of characters
        # smaller than index i
        for j in range ( ord ( str [i] ) - ord ( 'a' )):
            ct + = arr[j];
        
        ans[i] = ct;
    
    # print the count of characters smaller
    # than index i stored in ans array
    for i in range (n):
        print (ans[i], end = " " );
    
# Driver Code
 if __name__ = = '__main__' :
    str = "edcbaa" ;
    countSmaller( str );
    
# This code is contributed by Rajput-Ji

C #

 using System;
 class GFG
 {
 // Function to count the smaller
 // characters on the right of index i
 static void countSmaller(String str)
 {
    // store the length of String
    int n = str.Length; 
    // initialize each elements of
    // arr to zero
    int []arr = new int [26]; 
    // array to store count of smaller characters on
    // the right side of that index
    int []ans = new int [n]; 
    for ( int i = n - 1; i >= 0; i--)
    {
        arr[str[i] - 'a' ]++; 
        // initialize the variable to store
        // the count of characters smaller
        // than that at index i
        int ct = 0; 
        // adding the count of characters
        // smaller than index i
        for ( int j = 0; j < str[i] - 'a' ; j++)
        {
            ct += arr[j];
        }
        ans[i] = ct;
    }
    // print the count of characters smaller
    // than index i stored in ans array
    for ( int i = 0; i < n; i++)
    {
        Console.Write(ans[i] + " " );
    }
 }
 // Driver Code
 public static void Main(String[] args)
 {
    String str = "edcbaa" ;
    countSmaller(str);
 }
 }
 // This code is contributed by 29AjayKumar

Javascript

 <script>
 // Function to count the smaller
 // characters on the right of index i
 function countSmaller(str)
 {
    // store the length of string
    var n = str.length; 
    // initialize each elements of
    // arr to zero
    var arr = Array(26).fill(0); 
    // array to store count of smaller characters on
    // the right side of that index
    var ans = Array(n); 
    for ( var i = n - 1; i >= 0; i--) { 
        arr[str[i].charCodeAt(0) - 'a' .charCodeAt(0)]++; 
        // initialize the variable to store
        // the count of characters smaller
        // than that at index i
        var ct = 0; 
        // adding the count of characters
        // smaller than index i
        for ( var j = 0; j < str[i].charCodeAt(0) - 'a' .charCodeAt(0); j++) {
            ct += arr[j];
        }
        ans[i] = ct;
    }
    // print the count of characters smaller
    // than index i stored in ans array
    for ( var i = 0; i < n; i++) {
        document.write( ans[i] + " " );
    }
 }
 // Driver Code
 var str = "edcbaa" ;
 countSmaller(str);
 </script>

Выход:

 5 4 3 2 0 0

Сложность времени: O (N * 26)
Вспомогательное пространство: O (N + 26)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы

Количество лексикографически меньших символов справа

C ++

Ява

Python3

C #

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ