# CHFTNS -Editorial

Author and Editorialist Tejas Dhanait
Tester: Nandini Kapoor

# DIFFICULTY:

``````SIMPLE
``````

# PREREQUISITES:

``````Brute Force , Implementation
``````

# PROBLEM:

• A string Consisting of W and L is given, in which certain positions which are either divisible by K1 or K2 are locked. We can interchange the character of unlocked positions . We have to change the string in such a way that while traversing through the string the number of W appearing should always be strictly greater than the number of L appearing.
• If there are multiple strings present then we have to print lexiographically smallest one.

# EXPLANATION:

• We will maintain Two Counters For the count of W and L. Also We will maintain a vector ( we can even use stack, queue ) , in which we will push positions of all those characters which are āLā and for whose positions are neither divisible by K1 nor by K2.

• We are maintaining the vector as we want the modified string to be lexicographically smallest, and hence as L<W therefore we would try to change L to W (if required ) , as late as possible in the string

• So now while traversing through the string if anywhere the count of L becomes greater or equal to W then

1. if vector is empty then, it means we can not modify the string to a winning combination. Hence Print -1.
2. If vector is not empty then , we will change the last position present in the vector form L to W. Update the L and W counters accordingly. And pop back the position from the vector once that position has been modified from L to W.
• Finally if the winning combination is possible for the given string then print the number of characters changed in the string followed by the modified string in the next line.

# Time Complexity :

`````` O(N)
``````

# SOLUTIONS:

Setter's Solution (C++)
`````` /* Author : Tejas Dhanait ( tejas_1309) */
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test;
cin>>test;

while(test--)
{

string s;
cin>>s;
int k1,k2;
cin>>k1>>k2;

int win=0,lose=0;
int ans=0,flag=0;
vector<int> pos;

for(int i=0;i<s.length();i++)
{
if(s[i]=='L')
{
lose++;
if((i+1)%k1!=0 && (i+1)%k2!=0)
{
pos.push_back(i);
}
}
else
{
win++;
}

if(lose>=win)
{
if(pos.size()==0)
{
cout<<-1<<endl;
flag=1;
break;
}
else
{
int k=pos.back();
s[k]='W';
lose--;
win++;
pos.pop_back();
ans++;
}
}

}
if(flag==0)
{
cout<<ans<<endl;
cout<<s<<endl;
}

}

}
``````
Tester's Solution (Python)
``````t = int(input())
for _ in range(0,t):
s = input().
str = list(s)
k1,k2 = map(int,input().split())
w=0; l=0; flag=0; ans=0;
lis = []
for i in range(0,len(s)):
if str[i] == 'W':
w+=1
else:
l+=1
if (i+1)%k1!=0 and (i+1)%k2!=0:
lis.append(i)
if l>=w:
if len(lis) == 0:
flag=1
break
else:
str[lis[len(lis)-1]]='W'
lis.pop()
w+=1
l-=1
ans+=1
if flag: print(-1)
else:
print(ans)
for i in str:
print(i,end="")
print()
``````
5 Likes