You are given a string that is formed from only three characters ‘a’, ‘b’, ‘c’. You are allowed to change atmost ‘k’ characters in the given string while attempting to optimize the uniformity index.
Note : The uniformity index of a string is defined by the maximum length of the substring that contains same character in it.
Input
The first line of input contains two integers n (the size of string) and k. The next line contains a string of length n.
Output
A single integer denoting the maximum uniformity index that can be achieved.
Constraints
1 <= n <= 10^6
0 <= k <= n
String contains only ‘a’, ‘b’, ‘c’.
Sample Input 0
6 3
abaccc
Sample Output 0
6
Explanation
First 3 letters can be changed to ‘c’ and we can get the string ‘cccccc’
def anagram(str,k):
anag={}
for i in str:
if (i==’a’ or i==’b’ or i==’c’) == False:
return 0
if i not in anag.keys():
anag[i]=0
anag[i]=anag[i]+1
U_index=max(anag.values())
l=len(str)
l=l-U_index
if k<=l:
U_index+=k
else:
U_index+=l
print(U_index)
anagram(input(),int(input()))
def characterReplacement(s, k):
maxi=0
ans = 0
count = {}
for i in range(len(s)):
if s[i] not in count:
count[s[i]] = 1
else:
count[s[i]] += 1
maxi = max(maxi, count[s[i]])
if ans – maxi < k:
ans += 1
else:
count[s[i – ans]] -= 1
return ans
n,k = map(int,input().split())
s = input()
print(characterReplacement(s, k))
Ithis is not work hen a string is like:
10 3
aabbccaaa
your code fails at testcase abaaaabcbcbcbcbc
#include
using namespace std;
int main(){
long long int a,b,c,d,e,f,g,h=0,l,r,count,answer=0;
cin>>a>>b;
string kanishk;
cin>>kanishk;
for(c=0;c<3;c++){
char key='a'+c;
l=0;
r=0;count=0;
while(rb){
if(kanishk[l]!=key)
count–;
l++;
}
h=max(h,r-l+1);
++r;
}
answer=max(answer,h);
}
cout<<answer;
}
#Working Solution for all cases
def substring(l, letter):
maxi=-1
cnt=1
for i in range(len(l)-1):
if l[i]==letter and l[i]==l[i+1]:
cnt+=1
else:
cnt=1
if cnt>maxi:
maxi=cnt
return maxi
def count(s,k,letter):
maxi=-1
cnt=d[letter]
rem=len(s)-cnt
if rem<=k:
return len(s)
else:
slist=list(s)
srem=[i for i in range(len(slist)) if slist[i]!=letter]
for i in range(len(srem)-k+1):
slistC=slist.copy()
j=i
while jmaxi:
maxi=sublen
return maxi
n,k = list(map(int, input().strip().split()))
s = input()
d={‘a’:0,’b’:0,’c’:0}
for letter in s:
d[letter]+=1
aCount=count(s,k,’a’)
bCount=count(s,k,’b’)
cCount=count(s,k,’c’)
# print(aCount)
# print(bCount)
# print(cCount)
print(max([aCount,bCount,cCount]))
int main()
{
boost;
int i,n,k;
cin>>n>>k;
string str;
cin>>str;
int count = 1, maxi = 0;
char ch;
for(int i = 0, i < n-1, i++)
{
if(str[i] == str[i+1])
{
count++;
ch = str[i];
}
else
{
maxi = max(count,maxi);
count = 1;
}
}
maxi = max(count,maxi);
cout<<maxi+k;
return 0;
}
check for abbaca your code fails
my approach is to first find the substring which is uniform and is of the max length without any changes then to explore it’s left and right index and perform k changes
it does not work here
aabaaccc
k=1
any one want to practice the question you can practice here
https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/practice-problems/algorithm/uniformity-794d7bdc/description/?layout=old
n,k=list(map(int,input().split()))
s=input()
c1,c2,c3=0,0,0
l=0
r=-1
ans=0
temp=[0]*3
while l<n:
while rk:
break
ans=max(ans,c1+c2+c3)
if s[l]==’a’:
c1-=1
elif s[l]==’b’:
c2-=1
else:
c3-=1
l+=1
print(ans)
#include
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
string arr;
long long int d=0,p=0,f=0;
cin>>arr;
for(int i=0;i<a;i++){
if(arr[i]=='a')
p++;
else if(arr[i]=='b')
d++;
else if(arr[i]=='c')
f++;
}
long long int y,z;
y = max(p,d);
z = max(y,f);
cout<<z+b<<endl;
return 0;
}