Given string str containing only lowercase English alphabets of size N, the task is to find the substring having the maximum product.
Each English alphabet has a value such that val(‘a’) = 0, val(‘b’) = 1, val(‘c’) = 2, ……, val(‘z’) = 25.
Examples:
Input: str = “sdtfakdhdahdzz”
Output: hdzz
Here, the maximum product is for the substring “hdzz”.
product = 7 * 3 * 25 * 25 = 13125
Input: str = “neveropen”
Output: neveropen
Approach:
- First, traverse through the given string while maintaining a maximum product value.
- Product will always keep increasing or will remain constant unless we encounter an ‘a’. Hence, start a new substring after each ‘a’ occurrence.
- Also, along with the maximum product value, we will also maintain the substring to which the maximum product corresponds.
- Once the entire string has been traversed, print the substring corresponding to the maximum product.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!