Maximum Inequality | hackerearth solution

Problem

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

F(T) = number of indices  such that ${�}_{�}\ne {�}_{�+1}.$

You are given a binary string 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 ${�}_{1}$and ${�}_{2}$.must occur in the order they appear in S.

Find the maximum possible value of $�\left({�}_{1}\right)+�\left({�}_{2}\right).$

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 denoting the number of test cases. The description of T test cases is as follows:
• For each test case:
• The first line contains 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 $�\left({�}_{1}\right)+�\left({�}_{2}\right)$ in a separate line.

Constraints

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 $�\left({�}_{1}\right)+�\left({�}_{2}\right)=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 $�\left({�}_{1}\right)+�\left({�}_{2}\right)=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$�\left({�}_{1}\right)+�\left({�}_{2}\right)=0.$

Code(C++):-

#include<bits/stdc++.h>
using namespace std;
int solve (int n, string s) {
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.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
for(int x = 0;x<t;x++){
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:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-