Рубрики

Лексикографически наименьшая подстрока с максимальным количеством вхождений, содержащая только a и b

Учитывая строку (содержит символы от '0' до '9') и две цифры и , Задача состоит в том, чтобы найти подстроку в заданной строке с максимальным количеством вхождений и содержащей только a и b. Если есть две или более таких подстрок с одинаковыми частотами, выведите лексикографически наименьшее. Если такой подстроки не существует, выведите -1.

Примеры :

Input : str = "47", a = 4, b = 7 
Output : 4

Input : str = "23", a = 4, b = 7
Output : -1

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

Таким образом, идея состоит в том, чтобы вычислить частоту цифр 'a' и 'b' в строке, и ответом будет частота с максимальной частотой.

Примечание . Если обе цифры имеют одинаковую частоту, то ответом будет цифра, которая лексикографически меньше среди «а» и «b».

Ниже приведена реализация вышеуказанного подхода:

C ++

// CPP программа для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b

  
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b.

int maxFreq(string s, int a, int b)

{

    // Хранить частоту цифр

    int fre[10] = { 0 };

  

    // размер строки

    int n = s.size();

  

    // Взять лексикографически большую цифру в b

    if (a > b)

        swap(a, b);

  

    // получаем частоту каждого символа

    for (int i = 0; i < n; i++)

        fre[s[i] - '0']++;

  

    // Если такой строки нет

    if (fre[a] == 0 and fre[b] == 0)

        return -1;

  

    // Максимальная частота

    else if (fre[a] >= fre[b])

        return a;

    else

        return b;

}

  
// Драйвер программы

int main()

{

    int a = 4, b = 7;

  

    string s = "47744";

  

    cout << maxFreq(s, a, b);

  

    return 0;

}

Джава

// Java-программа для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b

  

import java.io.*;

  

class GFG {

  

  
// Функция для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b.

static int maxFreq(String s, int a, int b)

{

    // Хранить частоту цифр

    int fre[] =  new int[10];

  

    // размер строки

    int n = s.length();

  

    // Взять лексикографически большую цифру в b

    if (a > b)

    {

        int temp = a;

        a =b;

        b = temp;

      

    }

  

    // получаем частоту каждого символа

    for (int i = 0; i < n; i++)

        fre[s.charAt(i) - '0']++;

  

    // Если такой строки нет

    if (fre[a] == 0 && fre[b] == 0)

        return -1;

  

    // Максимальная частота

    else if (fre[a] >= fre[b])

        return a;

    else

        return b;

}

  
// Драйвер программы

  

    public static void main (String[] args) {

      

    int a = 4, b = 7;

  

    String s = "47744";

  

    System.out.print(maxFreq(s, a, b));

    }

}
// Этот код предоставлен inder_verma

python3

# Python 3 программа для поиска лексикографически
# наименьшая подстрока в данной строке с
# максимальная частота и содержит только a и b

  
# Функция для поиска лексикографически
# наименьшая подстрока в данной строке с
# максимальная частота и содержит только a и b.

def maxFreq(s, a, b):

    # Хранить частоту цифр

    fre = [0 for i in range(10)]

  

    # размер строки

    n = len(s)

  

    # Взять лексикографически большую цифру в б

    if (a > b):

        swap(a, b)

  

    # получить частоту каждого символа

    for i in range(0,n,1):

        a = ord(s[i]) - ord('0')

        fre[a] += 1

  

    # Если такой строки нет

    if (fre[a] == 0 and fre[b] == 0):

        return -1

  

    Максимальная частота

    elif (fre[a] >= fre[b]):

        return a

    else:

        return b

  
# Драйверная программа

if __name__ == '__main__':

    a = 4

    b = 7

  

    s = "47744"

  

    print(maxFreq(s, a, b))

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # программа для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b

using System;

  

class GFG {

  

  
// Функция для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b.

static int maxFreq(string s, int a, int b)

{

    // Хранить частоту цифр

    int []fre = new int[10];

  

    // размер строки

    int n = s.Length;

  

    // Взять лексикографически большую цифру в b

    if (a > b)

    {

        int temp = a;

        a =b;

        b = temp;

      

    }

  

    // получаем частоту каждого символа

    for (int i = 0; i < n; i++)

        fre[s[i] - '0']++;

  

    // Если такой строки нет

    if (fre[a] == 0 && fre[b] == 0)

        return -1;

  

    // Максимальная частота

    else if (fre[a] >= fre[b])

        return a;

    else

        return b;

}

  
// Драйвер программы

  

    public static void Main () {

      

    int a = 4, b = 7;

  

    string s = "47744";

  

     Console.WriteLine(maxFreq(s, a, b));

    }

}
// Этот код предоставлен inder_verma

PHP

<?php
// PHP-программа для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b

  
// Функция для поиска лексикографически
// наименьшая подстрока в данной строке с
// максимальная частота и содержит только a и b.

function maxFreq($s, $a, $b)

{

    // Хранить частоту цифр

    $fre = array_fill(0, 10, 0);

  

    // размер строки

    $n = strlen($s);

  

    // Взять лексикографически большую цифру в b

    if ($a > $b)

    {

        $xx = $a;

        $a = $b;

        $b = $xx;}

  

     // получаем частоту каждого символа

    for ($i = 0; $i < $n; $i++)

    {

        $a = ord($s[$i]) - ord('0');

        $fre[$a] += 1;

    }

  

    // Если такой строки нет

    if ($fre[$a] == 0 and $fre[$b] == 0)

        return -1;

  

    // Максимальная частота

    else if ($fre[$a] >= $fre[$b])

        return $a;

    else

        return $b;

}

  
// Код драйвера

$a = 4;

$b = 7;

  

$s = "47744";

  

print(maxFreq($s, $a, $b));

  
// Этот код предоставлен mits
?>

Выход:

4

Рекомендуемые посты:

Лексикографически наименьшая подстрока с максимальным количеством вхождений, содержащая только a и b

0.00 (0%) 0 votes