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