Codeforces #296 (Div. 2) B. Error Correct System

problem link – http://codeforces.com/contest/527/problem/B

This problem can be solved correctly if one knows to use the correct datastructure which will give a optimized solution.

here we use a 2D array called sameIndex

This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
if sameIndex[0][1]=1 then it means ‘a’ from String S and ‘b’ from String T are in same index
if sameIndex[1][0]=1 then it means ‘b’ from S and ‘a’ from T are in same index

There are 3 cases to look into

Case 1: perfect swapping pair is found and hamming distance is decremented by 2

Case 2: a swapping fair is found and hamming distance is decremented by 1

Case 3: hamming distance remains the same

These cases are explained in the code comments

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 100005
	typedef long long int ll;
	int main(){
	int n;
	string str1,str2;
	cin>>n;
	cin>>str1>>str2;
	//This 2D array is used to store mismatched characters from String S and String T respectively which are in the same index
	//if sameIndex[0][1]=1 then it means 'a' from String S and 'b' from String T are in same index
	//if sameIndex[1][0]=1 then it means 'b' from S and 'a' from T are in same index
	int sameIndex[26][26]={0};
	//The below array is used to store the indexes of the mismatched characters in string T
	//NOTE: String S and T are represented by str1 and str2 in the code and comments from now on
	int match[26];
	int ham=0;
	int f=0;
	pair<int,int> ans;
	memset(match,-1,sizeof match);
	REP(i,n){
	sameIndex[str1[i]-'a'][str2[i]-'a']=1;
	if(str1[i]!=str2[i]){
	match[str2[i]-'a']=i;
	ham++;
	}
	}
	REP(i,n){
	if(str1[i]!=str2[i]){
	//Case 1
	//If characters str1[i] and str2[i] are different
	//check if character str2[i] in string str1 and str1[i] in string str2 are present in same index
	//if present then the 2 characters can be swapped and thus hamming distance will be decremented by 2
	if(sameIndex[str2[i]-'a'][str1[i]-'a']){
	ham-=2;
	f=1;
	REP(j,n){
	if(str1[j]==str2[i]&&str2[j]==str1[i]){
	ans.first=i+1;
	ans.second=j+1;
	break;
	}
	}
	break;
	}
	}
	}
	if(!f){
	REP(i,n){
	//Case 2
	//check if mismatched character belonging to str1 is present in mismatched character set of str2
	//if present then we can swap str1[i] with the index where str1[i] is present in str2
	if(str1[i]!=str2[i]){
	if(match[str1[i]-'a']!=-1){
	f=1;
	ans.first=i+1;
	ans.second=match[str1[i]-'a']+1;
	ham--;
	break;
	}
	}
	}
	}
	cout<<ham<<endl;
	if(f){
	cout<<ans.first<<" "<<ans.second<<endl;
	}
	else{
	cout<<"-1 -1";
	}
	}

view raw Error Correct System.cpp hosted with ❤ by GitHub

Codeforces #211 (Div. 2) C.Fixing Typos

problem link: http://codeforces.com/problemset/problem/363/CA simple greedy approach will give you the solution.

A simple greedy approach will give you the solution.

Special care has to be taken for testcases like aabbccddeeff, aaaabbc

Code is self explanatory.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	//count in seperate vector and character in seperate vector
	//count1[i] denotes the count of character[i]
	vector<int>count1;
	vector<char>character;
	int main(){
	string str;
	cin>>str;
	REP(i,str.size()){
	char candidate=str[i];
	int c=1;
	for(int j=i+1;j<str.size();j++){
	if(candidate==str[j])
	c++;
	else
	break;
	}
	i+=(c-1);
	count1.pb(c);
	character.pb(candidate);
	}
	REP(i,count1.size()){
	if(count1[i]>=3)
	count1[i]=2;
	}
	REP(i,count1.size()-1){
	if(count1[i]==2&&count1[i+1]==2){
	count1[i+1]=1;
	}
	}
	REP(i,count1.size()){
	REP(j,count1[i]){
	cout<<character[i];
	}
	}
	}

view raw FixingTypos.cpp hosted with ❤ by GitHub

Checking if a given string S = nT

i.e to find if a given string can be represented from a substring by iterating it “n” times.

This can be done in O(N)

Let N=string length

Find all prime factors of N and for each prime factor p, consider candidate substring as  N/p length prefix of original string.

Check if the original string is repetition of candidate substring . This can be done in O(N).

Also number of prime factors of N (1<=N<=1 million) can be not more than 6. Hence we can safely say that the overall complexity is O(N).

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	vector<int> getPrimeFactors(int n){
	int limit=sqrt(n);
	vector<int> primeFactors;
	if(n%2==0){
	primeFactors.pb(2);
	n/=2;
	}
	while(n%2==0){
	n/=2;
	}
	for(int i=3;i<=limit;i+=2){
	if(n%i==0){
	primeFactors.pb(i);
	n/=i;
	}
	while(n%i==0){
	n/=i;
	}
	}
	if(n>2)
	primeFactors.pb(n);
	return primeFactors;
	}
	int main(){
	string str;
	cin>>str;
	int N=str.size();
	if(N>1){
	vector<int> p=getPrimeFactors(N);//get all prime factors of N(length of string)
	//for each factor p[i] check if prefix N/p[i] is the substring that is repeated
	string candidate;
	REP(i,p.size()){
	candidate=str.substr(0,p[i]);
	int k=0;
	int flag=1;
	FOR(j,p[i],N){
	if(candidate[k]==str[j]){
	k++;
	k%=candidate.size();
	}
	else{
	flag=0;
	break;
	}
	}
	if(flag){
	cout<<"Yes!";
	return 0;
	}
	}
	cout<<"No!";
	}
	else{
	cout<<"Not possible";
	}
	return 0;
	}

view raw checkifGivenStringSIsNT.cpp hosted with ❤ by GitHub

Removing duplicate elements in a string

This programs removes dulplicate elements in a string without using an additional array
//Time complexity O(n^2)
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
void removeDuplicate(char* str){
if(str==”)
return;
int pivot=1;
int len=strlen(str);
//i runs from 2nd element to last element because j runs from first element to pivot
//element and we need not compare same elements so i and j neve have same value at same time
for(int i=1;i<len;i++){
int j;
//make all elements before the pivot as unique

for(j=0;j<pivot;j++)
if(str[j]==str[i])
break;
if(j==pivot){
//if j==pivot (str to str+pivot) is a unique subarray where str[pivot]=str[i]

str[pivot]=str[i];
pivot++;
}

}
str[pivot]=”;

}
int main(){
char str[]=”asddfffafffafffafaffafaf”;
removeDuplicate(str);
cout<<str;

}