String Operations CodeChef Solution

Problem -String Operations CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

String Operations CodeChef Solution in C++17

 #include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
int main(){  
  ll k;
  cin>>k;
  while(k--){
     string str;
     cin>>str;
     ll n = str.size();
     set< vector<int> > one;
     for(int i=0;i<n;i++){   
         int sum = 0,count = 0;
         for(int j=i;j<n;j++){
             if(str[j] == '1')
             sum++;
             if(sum%2)
             count++;
             int len = j - i + 1;
             one.insert({len,sum,count});
         }
     }
     cout<<one.size()<<endl;
  }
  return 0;
} 

String Operations CodeChef Solution in C++14

#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int,int> v;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int t;
    cin>>t;
    while(t--){
        string s;   cin>>s;
        int n=s.length(),i,j;
        set<tuple<int,int,int>>st;
        for(int i=0;i<n;i++){
            int cnt=0,odd=0,evn=0;
            for(int j=i;j<n;j++){
                if(s[j]=='1'){
                    cnt++;
                }
                else{
                    if(cnt%2)   odd++;
                    else evn++;
                }
                int len= j-i+1;
                st.insert({len,evn,odd});
            }
        }
        cout<<st.size()<<endl;
    }   
    return 0;
}

String Operations CodeChef Solution in PYTH 3

# cook your dish here

for i in range(int(input())):
    st=input()
    s=set()
    for i in range(len(st)):
        ct=0
        even=0
        odd=0
        for j in range(i,len(st)):
            if(st[j]=="1"):
                ct+=1
            else:
                if(ct%2==0):
                    even+=1
                else:
                    odd+=1
            s.add((j-i+1,even,odd))
    print(len(s))
    s.clear()

String Operations CodeChef Solution in C

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

char sbuf[1003];
char *s = sbuf+1;

int gapsodd[1003];
int gapseven[1003];
int numofones[1003];

void preprocess(){
    memset(gapseven, 0, sizeof gapseven);
    memset(gapsodd, 0, sizeof gapsodd);
    memset(numofones, 0, sizeof numofones);

    int even = 1;
    int lastevensum = 0;
    int lastoddsum = 0;
    int lastnumofones = 0;
    for(int i = 0; s[i]; i++){
        if(s[i]=='1'){
            even = !even;
            lastnumofones++;
        }
        else if(even){
            lastevensum++;
        }else{
            lastoddsum++;
        }

        //1-based so 0-position is 0 always
        gapseven[i+1] = lastevensum;
        gapsodd[i+1] = lastoddsum;
        numofones[i+1] = lastnumofones;
    }
};


#define baisset(ba, i) ((ba)[(i)>>6] & (1ull << ((i) & 63))) != 0
#define baisclear(ba, i) ((ba)[(i)>>6] & (1ull << ((i) & 63))) == 0
#define baset(ba, i) (ba)[(i)>>6] |= (1ull << ((i) & 63))

uint64_t counts[1000][16];

int solve(int n) {
    int res = 0;

    for(int len = 1; len <= n; len++){
        memset(counts, 0, sizeof counts);
        int numones;
        int gaps;
        int even = 0;
        for(int i = 0, j = len; j <= n; i++, j++){
            numones = numofones[j]-numofones[i];
            if(s[i-1] == '1')
                even = !even;
            if(!numones){
                gaps = 0;
            }
            else if(even){
                gaps = gapseven[j] - gapseven[i];
            }else{
                gaps = gapsodd[j] - gapsodd[i];
            }
            if(baisclear(counts[numones], gaps)){
                baset(counts[numones], gaps);
                res++;
            }
        }
    }

    return res;
}

int main() {

    int t;
    scanf("%d", &t);

    while (t--){
        scanf("%s", s);
        preprocess();
        int res = solve(strlen(s));
        printf("%d\n", res);
    }


    return 0;
}

String Operations CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		try{
		      Scanner scan=new Scanner(System.in);
        int t= scan.nextInt();
        while(t>0){
          String a=scan.next();
            HashSet<ArrayList<Integer>> s=new HashSet<>();
            for(int i=0;i<a.length();i++){
                int count=0,even=0,odd=0;
                for(int j=i;j<a.length();j++){
                    if(a.charAt(j)=='1'){
                        count++;
                    }
                    else{
                        if(count%2==0){
                            even++;
                        }
                        else{
                            odd++;
                        }
                    }
                    int len=j-i+1;
                    ArrayList<Integer> x=new ArrayList<>();
                    x.add(len);
                    x.add(even);
                    x.add(odd);
                    s.add(x);
                }
            }
            System.out.println(s.size());
            t--;
        }
		}
		catch(Exception e){
		    return;
		}
	}
}

String Operations CodeChef Solution in PYPY 3

#impotm os
import sys
#from io impotm BytesIO, IOBase
#impotm itetmools
#impotm math
#impotm operator as op
#from functools impotm cmp_to_key
#impotm threading
#from heapq impotm heappop, heappush, heapify
#impotm random
#impotm bisect
#from queue impotm PriorityQueue, Queue 
#from collections impotm defaultdict, deque
#impotm random
#input = sys.stdin.readline
#def ic(n,a,s=0,st=1): return [a for i in range(s,n,st)]
#def ri(): return int(input())
#def sa(): return map(int,input().split())
#def ra(): return list(map(int,input().split()))
def mati(n): return [intl() for i in range(n)]
iinp = lambda: int(sys.stdin.readline())
inp  = lambda: sys.stdin.readline().strip()
strl = lambda: list(inp().strip().split(" "))
intl = lambda: list(map(int, inp().split(" ")))
mint = lambda: map(int, inp().split())
flol = lambda: list(map(float, inp().split(" ")))
flush = lambda: sys.stdout.flush()

def sll(s,size,non,n01,l,so1,se,n):
    sew=set()
    sew.add(((non,n01),(so1,se)))
    for i in range(size,n):
        if s[i-size]=='1':
            l.pop(0)
            se,so1=so1,se
            non-=1
        else:
            n01-=1
            l[0]-=1
            se-=1

        if s[i]=='1':
            non+=1
            l.append(0)
        else:
            n01+=1
            l[-1]+=1
            if len(l)&1:
                se+=1
            else:
                so1+=1
        sew.add(((non,n01),(so1,se)))
    return len(sew)

def substr(s,n,le):
    l=[]
    tm=non=n01=so1=se=cur=0
    for i in range(n):
        if s[i]=='0':
            if not cur&1:
                se+=1
            else:
                so1+=1
            tm+=1
            n01+=1
        else:
            l.append(tm)
            tm=0
            cur+=1
            non+=1
    l.append(tm)
    return sll(s,n,non,n01,l,so1,se,le)

for _ in range(iinp()):
    s=inp()
    n=len(s)
    ans=0
    for i in range(n):
        ans+=substr(s,i+1,n)
    print(ans)



        
'''
01101
9
10110
9
'''

        

String Operations CodeChef Solution in PYTH

from collections import deque

def get_key(s, i, j):
    count = 0
    arr = []
    
    for i in xrange(i, j):
        if s[i] == '0':
            if count % 2:
                arr.append('1')
                arr.append('0')
                count -= 1
            else:
                arr.append('0')
        else:
            count += 1
    
    arr += ['1'] * count
    
    i = len(arr)-1
    while i >= 0 and arr[i] == '1':
        i -= 1
    j = i-1
    while j >= 0 and arr[j] == '0':
        j -= 1
    k = j-1
    while k >= 0:
        if arr[k] == '1':
            arr[i] = '1'
            arr[j] = '0'
            arr[k-j+i] = '1'
            arr[k] = '0'
            i, j = i-1, k-j+i
        k -= 1

    return arr, i, j

def swap(arr, x, y, z, d):
    arr[x], arr[z] = arr[z], arr[x]
    arr[y], arr[z-y+x] = arr[z-y+x], arr[y]
    return x+d, z-y+x
    
def get_base_arr(s, i, j):
    arr = ['1' for _ in xrange(1005)]
    cq = deque()
    cq.append(0)
    
    k = count = 0
    for x in xrange(i, j):
        if s[x] == '0':
            if cq[-1]:
                cq.append(0)
            if count % 2:
                k += 1
                count -= 1
            arr[k] = '0'
            k += 1
        else:
            cq[-1] += 1
            count += 1
    
    x = k - 1
    while x >= 0 and arr[x] == '1':
        x -= 1
    y = x - 1
    while y >= 0 and arr[y] == '0':
        y -= 1
    z = y - 1
    while z >= 0:
        if arr[z] == '1':
            x, y = swap(arr, x, y, z, -1)
        z -= 1

    return cq, arr, x, y
    
def solve_fast(s):
    d = {}
    for i in xrange(1, len(s)+1):
        cq, arr, x, y = get_base_arr(s, 0, 0+i)
        y = max(y, -1)
        x = max(x, -1)
            
        d[(i, x, y)] = True
        
        #print i, ''.join(arr), 0, x, y
        
        z = 0
        for j in xrange(len(s)-i):
            w = -1
            if x+1 < z+i and s[j] == '1':
                if y > z:
                    _, y = swap(arr, x+1, y, z, 1)
                    x += 1
                if y < z and x >= z:
                    arr[x+1] = '0'
                    arr[x+2] = '0'
                    x += 2
                    
                    y = z + 1
                    arr[y] = '1'
                    
            x = max(x, z)
            y = max(y, z)
            arr[z] = 'X'
            z += 1
            
            w = y
            if s[j+i] == '0':
                if (z+i-x) % 2:
                    y = x + 1
                    x = y
                x += 1
                arr[x] = '0'
            else:
                arr[x+1] = '1'

            if w >= z and w != y:
                x, y = swap(arr, x, y, w, -1)
            
            #print i, ''.join(arr), z, x-z, y-z              
            d[(i, x-z, y-z)] = True
    
    #print d
    return len(d)

def solve(s):
    d = {}
    for i in xrange(1, len(s)+1):
        for j in xrange(len(s)-i+1):
            cq, arr, x, y = get_base_arr(s, j, j+i)
            
            x = max(x, -1)
            y = max(y, -1)
            #print i, ''.join(arr), 0, x, y
            d[(i, x, y)] = True
    
    #print d
    return len(d)
    
def main():
    t = int(raw_input())
    for _ in xrange(t):
        s = raw_input()
        print solve_fast(s)
        #cq, arr, x, y = get_base_arr(s, 0, len(s))
        #print cq
        #print ''.join(arr)
        #print x, y

if __name__ == '__main__':
    main()

String Operations CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace CompetitiveProgramming
{
    static class Solution
    {
        static StreamWriter output = new StreamWriter(Console.OpenStandardOutput());

        internal static void Main()
        {
            string testCountString = Console.ReadLine();
            if (string.IsNullOrEmpty(testCountString))
            {
                return;
            }
            int testCount = int.Parse(testCountString);
            for (int t = 0; t < testCount; t++)
            {
                var s = Console.ReadLine();
                var hashSet = new HashSet<Tuple<int, int, int>>();
                for (int i = 0; i < s.Length; i++)
                {
                    int oneCount = 0;
                    int odd = 0;
                    int even = 0;
                    for (int j = i; j < s.Length; j++)
                    {
                        if (s[j] == '1')
                        {
                            oneCount++;
                        }
                        else if ((oneCount & 1) == 1)
                        {
                            odd++;
                        }
                        else
                        {
                            even++;
                        }
                        hashSet.Add(Tuple.Create(j - i, odd, even));
                    }
                }
                output.WriteLine(hashSet.Count);
            }
            output.Flush();
        }
    }
}

String Operations CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)
	var buf bytes.Buffer
	for tc > 0 {
		tc--
		S, _ := reader.ReadString('\n')
		S = S[:len(S)-1]
		res := solve(S)
		buf.WriteString(fmt.Sprintf("%d\n", res))
	}
	fmt.Print(buf.String())
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func solve(S string) int {
	mem := make(map[Record]int)

	for i := 0; i < len(S); i++ {
		var ones int
		var cnt int
		for j := i; j < len(S); j++ {
			ones += int(S[j] - '0')
			cnt += ones & 1
			mem[Record{j - i + 1, ones, cnt}]++
		}
	}

	return len(mem)
}

type Record struct {
	length int
	ones   int
	cnt    int
}
String Operations CodeChef Solution Review:

In our experience, we suggest you solve this String Operations CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the String OperationsCodeChef Solution.

Find on CodeChef

Conclusion:

I hope this String Operations CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *