Given a string S of length N, the task is to find the maximum possible product of the first and the last character of the string if it is rotated any number of times toward left or right.
Examples:
Input: Str = “12345”
Output: 20
Explanation: If we rotate the string once in anticlockwise direction,
then the string becomes 51234, and the product = 5*4 = 20, which is the maximum.Input: Str = “86591”
Output: 48
Approach: This problem can be solved based on the following observation:
If the string is rotated i (i < N) times towards the left, the character at index (i-1) becomes the last and the character at index i becomes the first character.
From the above observation, we can conclude that the maximum product between two adjacent characters will be the answer. Follow the steps mentioned below to implement the idea:
- Store the product of the first and the last character of the original string as the current maximum product.
- Iterate over the string from i = 1 to N-1:
- Get the product of S[i] and S[i-1].
- If this is greater than the maximum value till now, update the maximum.
- The maximum value after the iteration is over is the required answer as seen above.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find maximum possible productint findMax(string& S){ int N = S.size(); int f = S[0] - '0'; int l = S[N - 1] - '0'; int Max = f * l; for (int i = 1; i < N; i++) { f = S[i] - '0'; l = S[i - 1] - '0'; Max = max(Max, f * l); } // Return the maximum product as the answer return Max;}// Driver Codeint main(){ string Str = "12345"; // Function Call cout << findMax(Str); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to find maximum possible product static int findMax(String S) { int N = S.length(); int f = (int)S.charAt(0) - (int)'0'; int l = (int)S.charAt(N - 1) - (int)'0'; int Max = f * l; for (int i = 1; i < N; i++) { f = (int)S.charAt(i) - (int)'0'; l = (int)S.charAt(i-1) - (int)'0'; Max = Math.max(Max, f * l); } // Return the maximum product as the answer return Max; } /* Driver program to test above function*/ public static void main(String args[]) { String Str = "12345"; // Function Call System.out.print(findMax(Str)); }}// This code is contributed by shinjanpatra. |
Python3
# Python3 code to implement the approach# Function to find maximum possible productdef findMax(S) : N = len(S); f = ord(S[0]) - ord('0'); l = ord(S[N - 1]) - ord('0'); Max = f * l; for i in range(1, N) : f = ord(S[i]) - ord('0'); l = ord(S[i - 1]) - ord('0'); Max = max(Max, f * l); # Return the maximum product as the answer return Max;# Driver Codeif __name__ == "__main__" : Str = "12345"; # Function Call print(findMax(Str)); # This code is contributed by AnkThon |
C#
/*package whatever //do not write package name here */using System;public class GFG{ // Function to find maximum possible product static int findMax(String S) { int N = S.Length; int f = (int)S[0] - (int)'0'; int l = (int)S[N - 1] - (int)'0'; int Max = f * l; for (int i = 1; i < N; i++) { f = (int)S[i] - (int)'0'; l = (int)S[i-1] - (int)'0'; Max = Math.Max(Max, f * l); } // Return the maximum product as the answer return Max; } /* Driver program to test above function*/ public static void Main(String []args) { String Str = "12345"; // Function Call Console.Write(findMax(Str)); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript code to implement the approach// Function to find maximum possible productfunction findMax(S){ let N = S.length; let f = S[0] - '0'; let l = S[N - 1] - '0'; let Max = f * l; for (let i = 1; i < N; i++) { f = S[i] - '0'; l = S[i - 1] - '0'; Max = Math.max(Max, f * l); } // Return the maximum product as the answer return Max;}// Driver Code let Str = "12345"; // Function Call document.write(findMax(Str)); // This code is contributed by satwik4409. </script> |
20
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!
