Minimum Number of Manipulations required to make two Strings Anagram Without Deletion of Character
Last Updated :
01 Sep, 2023
Given two strings s1 and s2, we need to find the minimum number of manipulations required to make two strings anagram without deleting any character.
Note:- The anagram strings have same set of characters, sequence of characters can be different.
If deletion of character is allowed and cost is given, refer to Minimum Cost To Make Two Strings Identical
Question Source: Yatra.com Interview Experience | Set 7
Examples:
Input :
s1 = "aba"
s2 = "baa"
Output : 0
Explanation: Both String contains identical characters
Input :
s1 = "ddcf"
s2 = "cedk"
Output : 2
Explanation : Here, we need to change two characters
in either of the strings to make them identical. We
can change 'd' and 'f' in s1 or 'e' and 'k' in s2.
Assumption: Length of both the Strings is considered similar
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
int countManipulations(string s1, string s2)
{
int count = 0;
int char_count[26];
for (int i = 0; i < 26; i++)
{
char_count[i] = 0;
}
for (int i = 0; i < s1.length(); i++)
char_count[s1[i] - 'a']++;
for (int i = 0; i < s2.length(); i++)
{
char_count[s2[i] - 'a']--;
}
for(int i = 0; i < 26; ++i)
{
if(char_count[i] != 0)
{
count+=abs(char_count[i]);
}
}
return count / 2;
}
int main()
{
string s1 = "ddcf";
string s2 = "cedk";
cout<<countManipulations(s1, s2);
}
|
Java
public class Similar_strings {
static int countManipulations(String s1, String s2)
{
int count = 0;
int char_count[] = new int[26];
for (int i = 0; i < s1.length(); i++)
char_count[s1.charAt(i) - 'a']++;
for (int i = 0; i < s2.length(); i++)
{
char_count[s2.charAt(i) - 'a']--;
}
for(int i = 0; i < 26; ++i)
{
if(char_count[i] != 0)
{
count+= Math.abs(char_count[i]);
}
}
return count / 2;
}
public static void main(String[] args)
{
String s1 = "ddcf";
String s2 = "cedk";
System.out.println(countManipulations(s1, s2));
}
}
|
Python3
def countManipulations(s1, s2):
count = 0
char_count = [0] * 26
for i in range(26):
char_count[i] = 0
for i in range(len( s1)):
char_count[ord(s1[i]) -
ord('a')] += 1
for i in range(len(s2)):
char_count[ord(s2[i]) - ord('a')] -= 1
for i in range(26):
if char_count[i] != 0:
count += abs(char_count[i])
return count / 2
if __name__ == "__main__":
s1 = "ddcf"
s2 = "cedk"
print(countManipulations(s1, s2))
|
C#
using System;
public class GFG {
static int countManipulations(string s1,
string s2)
{
int count = 0;
int []char_count = new int[26];
for (int i = 0; i < s1.Length; i++)
char_count[s1[i] - 'a']++;
for (int i = 0; i < s2.Length; i++)
char_count[s2[i] - 'a']--;
for(int i = 0; i < 26; ++i)
{
if(char_count[i] != 0)
{
count+= Math.Abs(char_count[i]);
}
}
return count / 2;
}
public static void Main()
{
string s1 = "ddcf";
string s2 = "cedk";
Console.WriteLine(
countManipulations(s1, s2));
}
}
|
Javascript
<script>
function countManipulations(s1, s2)
{
let count = 0;
let char_count = new Array(26);
for(let i = 0; i < char_count.length; i++)
{
char_count[i] = 0;
}
for(let i = 0; i < s1.length; i++)
char_count[s1[i].charCodeAt(0) -
'a'.charCodeAt(0)]++;
for(let i = 0; i < s2.length; i++)
{
char_count[s2[i].charCodeAt(0) -
'a'.charCodeAt(0)]--;
}
for(let i = 0; i < 26; ++i)
{
if (char_count[i] != 0)
{
count += Math.abs(char_count[i]);
}
}
return count / 2;
}
let s1 = "ddcf";
let s2 = "cedk";
document.write(countManipulations(s1, s2));
</script>
|
PHP
<?php
function countManipulations($s1, $s2)
{
$count = 0;
$char_count = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($s1); $i++)
$char_count[ord($s1[$i]) -
ord('a')] += 1;
for ($i = 0; $i < strlen($s2); $i++)
{
$char_count[ord($s2[$i]) -
ord('a')] -= 1;
}
for ($i = 0; $i < 26; $i++)
{
if($char_count[i]!=0)
{
$count+=abs($char_count[i]);
}
}
return ($count) / 2;
}
$s1 = "ddcf";
$s2 = "cedk";
echo countManipulations($s1, $s2);
?>
|
Time Complexity: O(n), where n is the length of the string.
Auxiliary Space: O(1).
Approach 2(Sorting and Comparing Characters Approach):
- Sort both strings in lexicographic order.
- Initialize a counter variable to zero.
- Iterate over both strings simultaneously and compare the characters at each position. If they’re not equal, increment the counter.
- Return the counter value divided by 2, since each manipulation affects two characters.
C++
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int countManipulations(string s1, string s2)
{
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
int i = 0, j = 0, count = 0;
while (i < s1.size() && j < s2.size())
{
if (s1[i] == s2[j])
{
i++;
j++;
}
else if (s1[i] < s2[j])
{
i++;
count++;
}
else
{
j++;
count++;
}
}
while (i < s1.size())
{
i++;
count++;
}
while (j < s2.size())
{
j++;
count++;
}
return count / 2;
}
int main()
{
string s1 = "ddcf";
string s2 = "cedk";
cout << countManipulations(s1, s2) << endl;
return 0;
}
|
Java
import java.util.Arrays;
public class StringManipulations {
public static int countManipulations(String s1, String s2) {
char[] s1Array = s1.toCharArray();
char[] s2Array = s2.toCharArray();
Arrays.sort(s1Array);
Arrays.sort(s2Array);
int i = 0, j = 0, count = 0;
while (i < s1Array.length && j < s2Array.length) {
if (s1Array[i] == s2Array[j]) {
i++;
j++;
} else if (s1Array[i] < s2Array[j]) {
i++;
count++;
} else {
j++;
count++;
}
}
count += (s1Array.length - i) + (s2Array.length - j);
return count / 2;
}
public static void main(String[] args) {
String s1 = "ddcf";
String s2 = "cedk";
System.out.println(countManipulations(s1, s2));
}
}
|
Python3
def count_manipulations(s1, s2):
s1_list = list(s1)
s2_list = list(s2)
s1_list.sort()
s2_list.sort()
i, j, count = 0, 0, 0
while i < len(s1_list) and j < len(s2_list):
if s1_list[i] == s2_list[j]:
i += 1
j += 1
elif s1_list[i] < s2_list[j]:
i += 1
count += 1
else:
j += 1
count += 1
count += len(s1_list) - i + len(s2_list) - j
return count // 2
if __name__ == "__main__":
s1 = "ddcf"
s2 = "cedk"
print(count_manipulations(s1, s2))
|
C#
using System;
public class StringManipulations
{
public static int CountManipulations(string s1, string s2)
{
char[] s1Array = s1.ToCharArray();
char[] s2Array = s2.ToCharArray();
Array.Sort(s1Array);
Array.Sort(s2Array);
int i = 0, j = 0, count = 0;
while (i < s1Array.Length && j < s2Array.Length)
{
if (s1Array[i] == s2Array[j])
{
i++;
j++;
}
else if (s1Array[i] < s2Array[j])
{
i++;
count++;
}
else
{
j++;
count++;
}
}
count += (s1Array.Length - i) + (s2Array.Length - j);
return count / 2;
}
public static void Main(string[] args)
{
string s1 = "ddcf";
string s2 = "cedk";
Console.WriteLine(CountManipulations(s1, s2));
}
}
|
Javascript
function countManipulations(s1, s2) {
const s1Array = s1.split('').sort();
const s2Array = s2.split('').sort();
let i = 0, j = 0, count = 0;
while (i < s1Array.length && j < s2Array.length) {
if (s1Array[i] === s2Array[j]) {
i++;
j++;
} else if (s1Array[i] < s2Array[j]) {
i++;
count++;
} else {
j++;
count++;
}
}
count += (s1Array.length - i) + (s2Array.length - j);
return Math.floor(count / 2);
}
const s1 = "ddcf";
const s2 = "cedk";
console.log(countManipulations(s1, s2));
|
Time Complexity:
- Sorting the strings takes O(n log n) time, where n is the length of the strings.
- Iterating over the sorted strings takes O(n) time.
- Therefore, the overall time complexity is O(n log n).
Space Complexity: O(n), where n is the length of the longer string. This is because we need to store the sorted versions of both strings in memory, which can take up to n space.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...