CareerCup

Assuming I can user Java's Arrays.sort():

import java.util.Arrays;

public class CanMatchAfterSwap {

	static boolean canMatch(String s1, String s2) {
		if (null == s1 || null == s1 || s1.length() != s2.length()) {
			return false;
		}
		// Extract and sort even or odd character strings from s1 and s2
		String s1e = evenOrOdd(true, s1);
		String s2e = evenOrOdd(true, s2);
		String s1o = evenOrOdd(false, s1);
		String s2o = evenOrOdd(false, s2);
		// If sorted extract match, it can be done
		return s1e.equals(s2e) && s1o.equals(s2o);
	}

	static String evenOrOdd(boolean even, String s) {
		int start = even ? 0 : 1;
		char[] result = new char[s.length() / 2 + 1];
		int j = 0;
		for (int i = start; i < s.length(); i = i + 2) {
			result[j++] = s.charAt(i);
		}
		Arrays.sort(result);
		return new String(result);
	}
	
	public static void main(String[] args) {
		System.out.println(canMatch("cdab", "abcd"));
		System.out.println(canMatch("dcba", "abcd"));
		System.out.println(canMatch("abcde", "cdeba"));
	}

}

const getevenAndOddFreqs = str => [...str].reduce(([evenFreqsAcc, oddFreqsAcc], char, i) => {
	if (i % 2) {
		return [{...evenFreqsAcc, [char]: (evenFreqsAcc[char] || 0) + 1}, oddFreqsAcc]
	}
	return [evenFreqsAcc, {...oddFreqsAcc, [char]: (oddFreqsAcc[char] || 0) + 1}] 
}, [{}, {}])

const areEquivalent = (str1, str2) => {
	if (str1.length !== str2.length) return false

	const [evenStr1Freqs, oddStr1Freqs]  = getEvenAndOddFreqs(str1)
	const [evenStr2Freqs, oddStr2Freqs] = getEvenAndOddFreqs(str2)

	return Object.keys(evenStr1Freqs).every(char => evenStr1Freqs[char] === evenStr2Freqs[char]) &&
	Object.keys(evenStr2Freqs).every(char => evenStr2Freqs[char] === evenStr1Freqs[char]) &&
	Object.keys(oddStr1Freqs).every(char => oddStr1Freqs[char] === oddStr2Freqs[char]) &&
	Object.keys(oddstr2Feqs).every(char => oddStr2Freqs[char] === oddStr2Freqs[char])

}

As soon as there's no operation that allows to swap a character on odd position with a character on even position, this problem can be split into two subproblems;
1) is a set of characters from odd positions of the first string equal to a set of characters from odd positions of the second string,
2) is a set of characters from even positions of the first string equal to a set of characters from even positions of the second string ?

Assuming that there're only lowercase letters, the code will look like:

std::array<int32_t, 26> odd_s1{}, odd_s2{};
  std::array<int32_t, 26> even_s1{}, even_s2{};

  auto count = [](const std::string &s, const int32_t begin,
                          std::array<int32_t, 26> &set) -> void {
                           for (int32_t i = begin, length = s.length(); i < length; i += 2) {
                               ++set[s[i] - 'a'];
                           }
                       };
    count(s1, 0, even_s1); count(s1, 1, odd_s1);
    count(s2, 0, even_s2); count(s2, 1, odd_s2);

    std::cout << s1 << " "
              << (even_s1 == even_s2 && odd_s1 == odd_s2 ? "" : "Not ")
              << "equivalent to "
              << s2 << '\n';

def can_match(x,b) :
m, n = map(len, [x,b])
if(m != n) : return False
def transform(x,b,k, trasx) :
# print(k, len(b))
if(x == b) : return True
if(k >= len(b)) : return False
k += 1
if(k < len(b)) :
if(k%2 == 0) :
for i in range(len(b)) :
if(i%2 == 0) :
trasx[i], b[k] = trasx[k], b[i]
if(True == transform(x,b,k,trasx) ) :
return True
trasx[i], b[k] = trasx[k], b[i]
if(True == transform(x,b,k,trasx) ) :
return True
else :
for i in range(len(b)) :
if(i%2 == 1) :
trasx[i], b[k] = trasx[k], b[i]
if(True == transform(x,b,k,trasx) ) :
return True
trasx[i], b[k] = trasx[k], b[i]
if(True == transform(x,b,k,trasx) ) :
return True
return False

return transform(x,b,-1, x)


print(can_match(list('cdab'), list('abcd')))
print(can_match(list('dcba'), list('abcd')))


# Given two string check if they can be made equivalent by performing some operations on one or both string.

# swapEven:swap a character at an even-numbered index with a character at another even-numbered index

# swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index

# Given : s="cdab" , x="abcd"
# s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"

#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;

bool CanBeMadeEqual(const string& a, const string& b)
{
    if (a.size() != b.size())
    {
        return false;
    }
    unordered_map<char, int> m;
    for (int offset = 0; offset < 2; ++offset)
    {
        for (int i = offset; i < a.size(); i += 2)
        {
            ++m[a[i]];
        }
        for (int i = offset; i < b.size(); i += 2)
        {
            --m[b[i]];
            if (m[b[i]] == 0)
            {
                m.erase(b[i]);
            }
            else if (m[b[i]] < 0)
            {
                break;
            }
        }
        if (!m.empty())
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cout << CanBeMadeEqual("cdab", "abcd") << "\n";
    cout << CanBeMadeEqual("dcba", "abcd") << "\n";
    cout << CanBeMadeEqual("abcd", "abcdcd") << "\n";
    return 0;
}

package cup.google;

public class StringManipulation {
	
	/*
		Given two string check if they can be made equivalent by performing some operations on one or both string. 
		
		swapEven:swap a character at an even-numbered index with a character at another even-numbered index 
		
		swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index 
		
		Given : s="cdab" , x="abcd" 
		s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd" 
		
		Given: s="dcba" , x="abcd" 
		no amount of operation will move character from an odd index to even index, so the two string will never be equals 
		
		Given: s="abcd" ,x="abcdcd" 
		x length to big so will never be equals


	 */
	

	public static void main(String[] args) {
		System.out.println(manipuateStrings("dcba", "abcd"));
	}
	
	
	/*  Logic
	 *  for each character of first string,
	 *  check if that char is in any even or odd position of the second string depending 
	 *  on the even or odd position of the 
	 *  first string char
	 */
	
	
	
	public static boolean manipuateStrings(String first, String second){
		
		if(first==null || second ==null ||first.length()!=second.length()) return false;
		
		char[] firstToChar = first.toCharArray();
		char[] secondToChar = second.toCharArray();
		boolean found;
		
		for(int i=0;i<first.length() ;i++){
			int j = (i%2==0)?0:1;
			found = false;
			for( ;j< second.length();j=j+2){
				
				if(firstToChar[i] == secondToChar[j]){
					found = true;
				}
			}
			
			if(!found) return false;
			
		}
		
		return true;
	}
}

Here's and O(N) solution with constant space

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define forup(i,a,b) for(i=(a); i<(b); ++i)
#define fordn(i,a,b) for(i=(a); i>(b); --i)
#define rep(i,a) for(i=0; i<(a); ++i)

#define gi(x) scanf("%d",&x)
#define gl(x) cin>>x
#define gd(x) scanf("%lf",&x)
#define gs(x) scanf(" %s",x)

#define fs first
#define sc second

#define pb push_back
#define mp make_pair

const int inf=numeric_limits<int>::max();
const LL linf=numeric_limits<LL>::max();

const int max_n=100;

char a[max_n], b[max_n];
int fe[26], fo[26], la, lb, i;

int main() {
    scanf("%s", a);
    scanf("%s", b);
    la = strlen(a);
    lb = strlen(b);
    if(la != lb){
        cout << "NO";
        return 0;
    }
    // Save frequencies of even and odd places +f for each char
    rep(i, la){
        if(i%2) fo[a[i]-'a']++;
        else fe[a[i]-'a']++;
    }
    // -f for each char
    rep(i, lb){
        if(i%2) fo[b[i]-'a']--;
        else fe[b[i]-'a']--;
    }
    // should be same for both a and b if fe and fo are 0
    rep(i, 26){
        if(fe[i]!=0 || fo[i]!=0){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

package Java;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 13/04/19
 * Description:
 * <p>
 * Given two string check if they can be made equivalent by performing some operations on one or both string.
 * <p>
 * swapEven:swap a character at an even-numbered index with a character at another even-numbered index
 * <p>
 * swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index
 * <p>
 * Given : s="cdab" , x="abcd"
 * s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"
 * <p>
 * Given: s="dcba" , x="abcd"
 * no amount of operation will move character from an odd index to even index, so the two string will never be equals
 * <p>
 * Given: s="abcd" ,x="abcdcd"
 * x length to big so will never be equals
 */
public class StringToStringTransformEvenOdd {

    public static void main(String args[]) {

        System.out.println(canTransform("abcd", "adcb"));
        System.out.println(canTransform("abcd", "dacb"));
        System.out.println(canTransform("adcba", "abcda"));
        System.out.println(canTransform("adcba", "bacda"));

    }

    private static boolean canTransform(String s1, String s2) {
        Map<Character, Integer> evenIndex = new HashMap<>();
        Map<Character, Integer> oddIndex = new HashMap<>();

        char s1Chars[] = s1.toCharArray();
        char s2Chars[] = s2.toCharArray();

        for (int i = 0; i < s1.length(); i++)
            if (i % 2 == 0)
                evenIndex.put(s1Chars[i], evenIndex.getOrDefault(s1Chars[i], 0) + 1);
            else
                oddIndex.put(s1Chars[i], oddIndex.getOrDefault(s1Chars[i], 0) + 1);

        for (int i = 0; i < s2.length(); i++)
            if (i % 2 == 0)
                evenIndex.put(s2Chars[i], evenIndex.getOrDefault(s2Chars[i], 0) - 1);
            else
                oddIndex.put(s2Chars[i], oddIndex.getOrDefault(s2Chars[i], 0) - 1);

        //evey value should be zero since they will cut each of them due to above count way
        return evenIndex.values().stream().filter(x -> x != 0).collect(Collectors.toList()).isEmpty()
                &&
                oddIndex.values().stream().filter(x -> x != 0).collect(Collectors.toList()).isEmpty();
    }
}

These are optimized solutions! Can anyone can tell me how to approach for Brute Force!