Maximum product of first and last character of String after rotation

View Discussion

Improve Article

Save Article

Like Article

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++

  

#include <bits/stdc++.h>

using namespace std;

  

int 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 Max;

}

  

int main()

{

    string Str = "12345";

  

    

    cout << findMax(Str);

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

By Julio MarchiPosted on