 # Editorial-Rotten Apples | ENCODING FEBRUARY 22

Author: Srinjoy Pal
Tester: Abhisekh Paul ,Sayan Poddar
Editorialist: Srinjoy Pal

MEDIUM

# PREREQUISITES:

Dynamic Programming, Prefix- Suffix

# PROBLEM:

We need to remove all the X from a string of O & X. Where for removing X from the beginning or end costs 1 unit and removing from between two elements costs 2 units.

# EXPLANATION:

For each i in S[i] from left we have two options :

• remove all the apples till S[i]. Total Cost = i +1.
• remove only that apple from the String. Total Cost= Previously Calculated Cost + 2.

Similarly from right we have the same options.

The TotalCost calculated and stored for both the cases, now we have to find the minimum cost for each i to be removed from the string.
Two possible outcomes are there:

• remove some from left. The TotalCost is calculated and stored in left array.
• remove from right to i+1 . The TotalCost is calculated in right array.
We have to find the minimum for each i and add it to the Answer.

O(n)

O(n)

# SOLUTION:

Setter's Solution: C++
``````#include <bits/stdc++.h>
using namespace std;
int main(){
ll t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int n = s.size();
int ans= INT_MAX;
vector<int>l(n,0) , r(n,0);
if(s=='X')
l = 1;
for(int i=1;i<n;i++)
{
if(s[i]=='X')

l[i] = min(l[i-1]+2 , i+1);
else
l[i] = l[i-1];
}

if(s[n-1]=='X')
r[n-1]=1;
for(int i=n-2;i>=0;i--)
{
if(s[i]=='X')
r[i] = min(r[i+1]+2,n-i);
else
r[i] = r[i+1];
}

ans = min(l[n-1],r);
for(int i=0;i<=n-2;i++)
{
ans = min(ans , l[i] + r[i+1]);
}
cout<<ans<<endl;
}
return 0;
}
``````
Tester's Solution: Python
``````def solve():
s = input()
l = len(s)
p = l
c = 0
for i in range(l):
if s[i]=='X':
c = min(c+2,i+1)
p = min(p,c+l-i-1)
print(p)
``````

t = int(input())
while(t>0):
solve()
t -= 1

Tester's Solution: Java
``````import java.util.*;
class Feb6
{
public static void  main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(sc.nextLine());
while(t>0)
{
String s[]=sc.nextLine().split("");
int l=s.length;
int p=l;
int c=0;
for(int i=0;i<l;i++)
{
if(s[i].equals("X"))
{
c=Math.min(c+2,i+1);
}
p = Math.min(p,c+l-i-1);
}
System.out.println(p);
t--;

}
}
}
``````