Encuentre la substring con el producto máximo

Dada la string str que contiene solo alfabetos ingleses en minúsculas de tamaño N , la tarea es encontrar la substring que tiene el producto máximo. 
 

Cada alfabeto inglés tiene un valor tal que val(‘a’) = 0, val(‘b’) = 1, val(‘c’) = 2, ……, val(‘z’) = 25 .

Ejemplos: 
 

Entrada: str = “sdtfakdhdahdzz” 
Salida: hdzz 
Aquí, el producto máximo es para la substring “hdzz”. 
producto = 7 * 3 * 25 * 25 = 13125
Entrada: str = “geeksforgeeks” 
Salida: geeksforgeeks 
 

Acercarse: 
 

• Primero, recorra la string dada mientras mantiene un valor de producto máximo.
• El producto siempre seguirá aumentando o permanecerá constante a menos que encontremos una ‘a’ . Por lo tanto, comience una nueva substring después de cada aparición de ‘a’ .
• Además, junto con el valor del producto máximo, también mantendremos la substring a la que corresponde el producto máximo.
• Una vez recorrida toda la string, imprima la substring correspondiente al producto máximo.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the maximum product substring
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the value of a character
int value(char x)
{
    return (int)(x - 'a');
}
 
// Function to find the maximum product substring
string maximumProduct(string str, int n)
{
    // To store substrings
    string answer = "", curr = "";
    long long maxProduct = 0, product = 1;
 
    for (int i = 0; i < n; i++) {
        product *= 1LL * value(str[i]);
 
        curr += str[i];
 
        // Check if current product is maximum
        // possible or not
        if (product >= maxProduct) {
            maxProduct = product;
            answer = curr;
        }
 
        // If product is 0
        if (product == 0) {
            product = 1;
            curr = "";
        }
    }
 
    // Return the substring with maximum product
    return answer;
}
 
// Driver code
int main()
{
    string str = "sdtfakdhdahdzz";
 
    int n = str.size();
 
    // Function call
    cout << maximumProduct(str, n) << endl;
 
    return 0;
}

// Java program to find the maximum product subString
 
class GFG{
  
// Function to return the value of a character
static int value(char x)
{
    return (int)(x - 'a');
}
  
// Function to find the maximum product subString
static String maximumProduct(String str, int n)
{
    // To store subStrings
    String answer = "", curr = "";
    long maxProduct = 0, product = 1;
  
    for (int i = 0; i < n; i++) {
        product *= 1L * value(str.charAt(i));
  
        curr += str.charAt(i);
  
        // Check if current product is maximum
        // possible or not
        if (product >= maxProduct) {
            maxProduct = product;
            answer = curr;
        }
  
        // If product is 0
        if (product == 0) {
            product = 1;
            curr = "";
        }
    }
  
    // Return the subString with maximum product
    return answer;
}
  
// Driver code
public static void main(String[] args)
{
    String str = "sdtfakdhdahdzz";
  
    int n = str.length();
  
    // Function call
    System.out.print(maximumProduct(str, n) +"\n");
  
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the maximum product sub
 
# Function to return the value of a character
def value(x):
    return (ord(x) - ord('a'))
 
# Function to find the maximum product sub
def maximumProduct(strr, n):
 
    # To store subs
    answer = ""
    curr = ""
    maxProduct = 0
    product = 1
 
    for i in range(n):
        product *=value(strr[i])
 
        curr += strr[i]
 
        # Check if current product is maximum
        # possible or not
        if (product >= maxProduct):
            maxProduct = product
            answer = curr
 
        # If product is 0
        if (product == 0):
            product = 1
            curr = ""
 
    # Return the sub with maximum product
    return answer
 
# Driver code
if __name__ == '__main__':
    strr = "sdtfakdhdahdzz"
 
    n = len(strr)
 
    # Function call
    print(maximumProduct(strr, n))
 
# This code is contributed by mohit kumar 29

// C# program to find the maximum product subString
 
using System;
 
public class GFG{
 
// Function to return the value of a character
static int value(char x)
{
    return (int)(x - 'a');
}
 
// Function to find the maximum product subString
static String maximumProduct(String str, int n)
{
    // To store subStrings
    String answer = "", curr = "";
    long maxProduct = 0, product = 1;
 
    for (int i = 0; i < n; i++) {
        product *= 1L * value(str[i]);
 
        curr += str[i];
 
        // Check if current product is maximum
        // possible or not
        if (product >= maxProduct) {
            maxProduct = product;
            answer = curr;
        }
 
        // If product is 0
        if (product == 0) {
            product = 1;
            curr = "";
        }
    }
 
    // Return the subString with maximum product
    return answer;
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "sdtfakdhdahdzz";
 
    int n = str.Length;
 
    // Function call
    Console.Write(maximumProduct(str, n) +"\n");
 
}
}
// This code is contributed by PrinciRaj1992

<script>
// Javascript program to find the
// maximum product subString
 
// Function to return the value of a character
function value(x)
{
    return (x.charCodeAt() - 'a'.charCodeAt());
}
    
// Function to find the maximum product subString
function maximumProduct(str, n)
{
    // To store subStrings
    let answer = "", curr = "";
    let maxProduct = 0, product = 1;
    
    for (let i = 0; i < n; i++) {
        product *= (1 * value(str[i]));
    
        curr += str[i];
    
        // Check if current product is maximum
        // possible or not
        if (product >= maxProduct) {
            maxProduct = product;
            answer = curr;
        }
    
        // If product is 0
        if (product == 0) {
            product = 1;
            curr = "";
        }
    }
    
    // Return the subString with maximum product
    return answer;
}
    
 
// Driver Code
 
     let str = "sdtfakdhdahdzz";
    
    let n = str.length;
    
    // Function call
    document.write(maximumProduct(str, n) +"<br/>");
     
</script>

hdzz

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)