La substring lexicográficamente más pequeña con un máximo de ocurrencias que contienen solo a y b

Dada una string  (que contiene caracteres del ‘0’ al ‘9’) y dos dígitos  y  . La tarea es encontrar la substring en la string dada con el máximo de ocurrencias y que contenga solo a y b. Si hay dos o más de estas substrings con las mismas frecuencias, imprima la lexicográficamente más pequeña. Si no existe tal substring, imprima -1. 
Ejemplos : 
 

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

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

La idea es observar que necesitamos encontrar la substring con el máximo número de ocurrencias. Entonces, si consideramos las substrings que contienen tanto a como b, entonces el número de ocurrencias será menor que si consideramos las substrings con un solo dígito ‘a’ y ‘b’ individualmente.
Entonces, la idea es calcular la frecuencia de los dígitos de ‘a’ y ‘b’ en la string y el de máxima frecuencia será la respuesta.
Nota : si ambos dígitos tienen la misma frecuencia, la respuesta será el dígito lexicográficamente más pequeño entre ‘a’ y ‘b’.
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only.
int maxFreq(string s, int a, int b)
{
    // To store frequency of digits
    int fre[10] = { 0 };
 
    // size of string
    int n = s.size();
 
    // Take lexicographically larger digit in b
    if (a > b)
        swap(a, b);
 
    // get frequency of each character
    for (int i = 0; i < n; i++)
        fre[s[i] - '0']++;
 
    // If no such string exits
    if (fre[a] == 0 and fre[b] == 0)
        return -1;
 
    // Maximum frequency
    else if (fre[a] >= fre[b])
        return a;
    else
        return b;
}
 
// Driver program
int main()
{
    int a = 4, b = 7;
 
    string s = "47744";
 
    cout << maxFreq(s, a, b);
 
    return 0;
}

// Java program to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only
 
import java.io.*;
 
class GFG {
 
 
// Function to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only.
static int maxFreq(String s, int a, int b)
{
    // To store frequency of digits
    int fre[] =  new int[10];
 
    // size of string
    int n = s.length();
 
    // Take lexicographically larger digit in b
    if (a > b)
    {
        int temp = a;
        a =b;
        b = temp;
     
    }
 
    // get frequency of each character
    for (int i = 0; i < n; i++)
        fre[s.charAt(i) - '0']++;
 
    // If no such string exits
    if (fre[a] == 0 && fre[b] == 0)
        return -1;
 
    // Maximum frequency
    else if (fre[a] >= fre[b])
        return a;
    else
        return b;
}
 
// Driver program
 
    public static void main (String[] args) {
     
    int a = 4, b = 7;
 
    String s = "47744";
 
    System.out.print(maxFreq(s, a, b));
    }
}
// This code is contributed by inder_verma

# Python 3 program to Find the lexicographically
# smallest substring in a given string with
# maximum frequency and contains a's and b's only
 
# Function to Find the lexicographically
# smallest substring in a given string with
# maximum frequency and contains a's and b's only.
def maxFreq(s, a, b):
    # To store frequency of digits
    fre = [0 for i in range(10)]
 
    # size of string
    n = len(s)
 
    # Take lexicographically larger digit in b
    if (a > b):
        swap(a, b)
 
    # get frequency of each character
    for i in range(0,n,1):
        a = ord(s[i]) - ord('0')
        fre[a] += 1
 
    # If no such string exits
    if (fre[a] == 0 and fre[b] == 0):
        return -1
 
    # Maximum frequency
    elif (fre[a] >= fre[b]):
        return a
    else:
        return b
 
# Driver program
if __name__ == '__main__':
    a = 4
    b = 7
 
    s = "47744"
 
    print(maxFreq(s, a, b))
 
# This code is contributed by
# Surendra_Gangwar

// C# program to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only
using System;
 
class GFG {
 
 
// Function to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only.
static int maxFreq(string s, int a, int b)
{
    // To store frequency of digits
    int []fre = new int[10];
 
    // size of string
    int n = s.Length;
 
    // Take lexicographically larger digit in b
    if (a > b)
    {
        int temp = a;
        a =b;
        b = temp;
     
    }
 
    // get frequency of each character
    for (int i = 0; i < n; i++)
        fre[s[i] - '0']++;
 
    // If no such string exits
    if (fre[a] == 0 && fre[b] == 0)
        return -1;
 
    // Maximum frequency
    else if (fre[a] >= fre[b])
        return a;
    else
        return b;
}
 
// Driver program
 
    public static void Main () {
     
    int a = 4, b = 7;
 
    string s = "47744";
 
     Console.WriteLine(maxFreq(s, a, b));
    }
}
// This code is contributed by inder_verma

<?php
// PHP program to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only
 
// Function to Find the lexicographically
// smallest substring in a given string with
// maximum frequency and contains a's and b's only.
function maxFreq($s, $a, $b)
{
    // To store frequency of digits
    $fre = array_fill(0, 10, 0);
 
    // size of string
    $n = strlen($s);
 
    // Take lexicographically larger digit in b
    if ($a > $b)
    {
        $xx = $a;
        $a = $b;
        $b = $xx;}
 
     // get frequency of each character
    for ($i = 0; $i < $n; $i++)
    {
        $a = ord($s[$i]) - ord('0');
        $fre[$a] += 1;
    }
 
    // If no such string exits
    if ($fre[$a] == 0 and $fre[$b] == 0)
        return -1;
 
    // Maximum frequency
    else if ($fre[$a] >= $fre[$b])
        return $a;
    else
        return $b;
}
 
// Driver Code
$a = 4;
$b = 7;
 
$s = "47744";
 
print(maxFreq($s, $a, $b));
 
// This code is contributed by mits
?>

<script>
      // JavaScript program to Find the lexicographically
      // smallest substring in a given string with
      // maximum frequency and contains a's and b's only
      // Function to Find the lexicographically
      // smallest substring in a given string with
      // maximum frequency and contains a's and b's only.
      function maxFreq(s, a, b)
      {
       
        // To store frequency of digits
        var fre = new Array(10).fill(0);
 
        // size of string
        var n = s.length;
 
        // Take lexicographically larger digit in b
        if (a > b) {
          var temp = a;
          a = b;
          b = temp;
        }
 
        // get frequency of each character
        for (var i = 0; i < n; i++)
          fre[s[i].charCodeAt(0) - "0".charCodeAt(0)]++;
 
        // If no such string exits
        if (fre[a] === 0 && fre[b] === 0) return -1;
         
        // Maximum frequency
        else if (fre[a] >= fre[b]) return a;
        else return b;
      }
 
      // Driver program
      var a = 4,
        b = 7;
      var s = "47744";
      document.write(maxFreq(s, a, b));
       
      // This code is contributed by rdtank.
    </script>

4

Complejidad temporal: O(n), donde n es la longitud de la string s.

Espacio Auxiliar: O(10)