## Google Interview Question

Software Engineers**Country:**United States

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"

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"));
}
}
```

```
#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;
}
}
```

- Anonymous August 10, 2018