Header Ads Widget

Maximum Inequality | hackerearth solution

Rajnish Tripathi 21:51
Problem

A function on a binary string T of length M is defined as follows:

F(T) = number of indices � (1≤�<�) such that ��≠��+1.

You are given a binary string S of length N. You have to divide string S into two subsequences �1,�2 such that:

  • Each character of string S belongs to one of �1 and �2.
  • The characters of �1and �2.must occur in the order they appear in S.

Find the maximum possible value of �(�1)+�(�2).

NOTE: A binary string is a string that consists of characters `0` and `1`. One of the strings �1, �2 can be empty.

Input format

  • The first line contains T denoting the number of test cases. The description of T test cases is as follows:
  • For each test case:
    • The first line contains N denoting the size of string S.
    • The second line contains the string S.

Output format
For each test case, print the maximum possible value of �(�1)+�(�2) in a separate line.

Constraints

1≤�≤1051≤�≤105∣�∣=�����������ℎ�������� ′0′ ��� ′1′.�����������������������������������2⋅105.

Sample Input
3
3
011
4
1100
5
11111
Sample Output
1
2
0
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The first test case

  • One possible division is �1=011,�2="" (empty string). Here �(�1)+�(�2)=1+0=1. There is no way to divide the given string to obtain a greater answer.

The second test case

  • The optimal division is �1=10,�2=10. Here �(�1)+�(�2)=1+1=2. There is no way to divide the given string to obtain a greater answer. 

The third test case

  • For any possible division of S, �(�1)+�(�2)=0. 

 Code(C++):-

#include<bits/stdc++.h>
using namespace std;
int solve (int n, string s) {
// Write your code here
string s1 = "", s2 = "";
s1 += s[0];
bool flag = 0;
if(s[0]=='0') flag = 1;
for(int i=1;i<n;i++){
if(flag){
if(s[i] == '1'){
s1 += '1';
flag = 0;
}
else {
s2 += '0';
}
}
else{
if(s[i] == '0'){
s1 += '0';
flag = 1;
}
else {
s2 += '1';
}
}
}
//cout<<s1<<" "<<s2;
int ans = 0,n2 = s2.length();
for(int i=1;i<n2;i++){
if(s2[i]!=s2[i-1]) ans++;
}
ans += s1.length()-1;
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for(int t_i = 0; t_i < T; t_i++)
{
int N;
cin >> N;
string S;
cin >> S;
int out_;
out_ = solve(N, S);
cout << out_;
cout << "\n";
}
}

Code(JAVA):-

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
//BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = (int)Integer.parseInt(br.readLine());
for(int x = 0;x<t;x++){
int n = (int)Integer.parseInt(br.readLine());
String s = br.readLine();
String[] subs = subStrings(s);
int subsval = function(subs[0]) + function(subs[1]);
System.out.println(subsval);
}
}
public static int function(String s){
if(s.length()<2) return 0;
char[] carray = s.toCharArray();
int result = 0;
for(int i=0;i<s.length()-1;i++){
if(carray[i]!=carray[i+1]) result++;
}
return result;
}
public static String[] subStrings(String s){
String[] subs = new String[2];
StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
sb1.append(s.charAt(0));
char prev = s.charAt(0);
for(int i =1;i<s.length();i++){
if(s.charAt(i)!=prev){
sb1.append(s.charAt(i));
prev = s.charAt(i);
}
else sb2.append(s.charAt(i));
}
subs[0] = sb1.toString();
subs[1] = sb2.toString();
return subs;
}
}


Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments