Find the longest Sequence of apples
There is a string of size N containing only ‘A’ and ‘O’. ‘A’ stands for Apple, and ‘O’ stands for Orange. We have M number of spells, each spell allows us to convert an orange into an apple. Find the longest sequence of apples you can make, given a string and the value of M.
Examples:
Input: N = 5, M = 1, arr[] = ‘AAOAO’
Output: 4
Explanation: Changing the orange at the 3rd position into an apple gives us the maximum possible answer.Input: N = 5, M = 1, arr = ‘AOOAO’
Output: 2
Explanation: Changing any orange into an apple will give us a sequence of length 2.
Approach: To solve the problem follow the below idea:
We will create some variables to store the left index, right index, number of oranges, and maximum length and we will traverse the string and will count the number of oranges present, and will calculate the max number of adjacent apples.
Follow the steps to solve the problem:
- Initialize variables to store left index, right index, number of oranges, and maximum length
- Start while loop with condition right index < length of the string and check if the char at that index is orange if orange then increments the count of orange by 1.
- Start another while loop inside the loop and check if the count of orange > the given value of maximum possible replacement if it is greater then decrease the count by 1 it will repeat the unit condition and get false.
- Outside the inner while loop, we will calculate the maximum length for each iteration of the outer while loop and assign it to maxi length and then increase the right index by 1.
- The outer while loop will run for the total length of the string and update the maximum length in each iteration.
Below is the code implementation of the above approach.
C++14
#include <bits/stdc++.h> using namespace std; int appleSequence( int n, int m, string arr) { int left = 0; int right = 0; // It will store maximum // length of apple int max_len = 0; // It will count number // of oranges int orange = 0; // Stopping condition // for while loop while (right < arr.length()) { // If we found orange at // some index right if (arr[right] == 'O' ) { // Increament count of // orange by 1 orange++; } // Stopping condition for // while loop while (orange > m) { // Now we will change orange // to apple and will start // from starting of string // and check where orange // is present if (arr[left] == 'O' ) { // We will decrease // count and so it // increase apple orange--; } // Increment left by 1 left++; } // Calculating maximum length max_len = max(max_len, right - left + 1); right++; } // It will return maximum value return max_len; } // Drivers code int main() { string arr = "AAOAO" ; int N = 5; int M = 1; cout << appleSequence(N, M, arr) << endl; return 0; } |
Java
import java.io.*; class GfG { public static int appleSequence( int n, int m, String arr) { // Code here int left = 0 ; int right = 0 ; // It will store maximum // length of apple int max = 0 ; // It will count number // of oranges int orange = 0 ; // Stopping condition // for while loop while (right < arr.length()) { // If we found orange at // some index right if (arr.charAt(right) == 'O' ) { // Increament count of // orange by 1 orange++; } // Stopping condition for // while loop while (orange > m) { // Now we will change orange // to apple and will start // from starting of string // and check where orange // is present if (arr.charAt(left) == 'O' ) { // We will decrease // count and so it // increase apple orange--; } // Increment left by 1 left++; } // Calculating maximum length max = Math.max(max, right - left + 1 ); right++; } // It will return maximum value return max; } // Drivers code public static void main(String[] args) { String arr = "AAOAO" ; int N = 5 ; int M = 1 ; System.out.println(appleSequence(N, M, arr)); } } |
Python3
# Python3 code for the approach # Function to return length longest Sequence of apples def apple_sequence(n: int , m: int , arr: str ) - > int : left = 0 right = 0 # It will store maximum # length of apple max_len = 0 # It will count number # of oranges orange = 0 # Stopping condition # for while loop while right < len (arr): # If we found orange at # some index right if arr[right] = = 'O' : # Increament count of # orange by 1 orange + = 1 # Stopping condition for # while loop while orange > m: # Now we will change orange # to apple and will start # from starting of string # and check where orange # is present if arr[left] = = 'O' : # We will decrease # count and so it # increase apple orange - = 1 # Increment left by 1 left + = 1 # Calculating maximum length max_len = max (max_len, right - left + 1 ) right + = 1 # It will return maximum value return max_len # Drivers code if __name__ = = '__main__' : arr = "AAOAO" N = 5 M = 1 print (apple_sequence(N, M, arr)) |
C#
// C# code for the approach using System; class GFG { // Function to find the length of the longest // contiguous subsequence with at most m oranges static int appleSequence( int n, int m, string arr) { int left = 0; int right = 0; // It will store maximum // length of apple int max_len = 0; // It will count number // of oranges int orange = 0; // Stopping condition for while loop while (right < arr.Length) { // If we found orange at // some index right if (arr[right] == 'O' ) { // Increament count of // orange by 1 orange++; } // Stopping condition for // while loop while (orange > m) { // Now we will change orange // to apple and will start // from starting of string // and check where orange // is present if (arr[left] == 'O' ) { // We will decrease // count and so it // increase apple orange--; } // Increment left by 1 left++; } // Calculating maximum length max_len = Math.Max(max_len, right - left + 1); right++; } // It will return maximum value return max_len; } // Driver Code public static void Main() { string arr = "AAOAO" ; int N = 5; int M = 1; Console.WriteLine(appleSequence(N, M, arr)); } } |
Javascript
// JavaScript code // Function to return length longest Sequence of apples function appleSequence(n, m, arr) { let left = 0; let right = 0; // It will store maximum // length of apple let max_len = 0; // It will count number // of oranges let orange = 0; // Stopping condition // for while loop while (right < arr.length) { // If we found orange at // some index right if (arr[right] === "O" ) { // Increament count of // orange by 1 orange++; } // Stopping condition for // while loop while (orange > m) { // Now we will change orange // to apple and will start // from starting of string // and check where orange // is present if (arr[left] === "O" ) { // We will decrease // count and so it // increase apple orange--; } // Increment left by 1 left++; } // Calculating maximum length max_len = Math.max(max_len, right - left + 1); right++; } // It will return maximum value return max_len; } // Drivers code let arr = "AAOAO" ; let N = 5; let M = 1; console.log(appleSequence(N, M, arr)); |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us