mujain Very poor description of a simple problem..I am not sure what are we achieving by complicating the problem description.. what was the significance of length 'a' and 'b'when in example it already calls out it should be equal length in order to be anagram. This is merely making it verbose and adding complexities like |a-b| < 1 .. not contributing to the gut of the problem. My suggestion is to remove this problem or modify signifincantly. only reason I can see to keep it as is if we intent to confuse reader.
nixomose Agreed. It took me longer to understand the question than it did to write a solution.
[DELETED] [deleted]
Maher_Saleem agreed
meacreatio Agreed - and this question is not unique in this. Many questions on this site are harder to understand than they are to solve.
ealeksandro I was about to say the same thing. Surprising that after two years, nobody corrected the problem.
|S1.len-S2.len| must be 0 or S1,S2 can't be an anagram.
hiteshmadhyan191 same again after two years.
nguyenquan2707 Agreed.
hiteshmadhyan191 [deleted]
richard_luo06951 This is how real-world problems look like. You have to analyze it
andadeacu I agree to delete this problem.
edrouwendaal I agree on this also leaving a wrong test case, blocks one's logic. In real life of course this could happen. Or during job interview questions. But for just training skills it's not the best question.
deeteecee Why not just split the input by a space to make it more understandable rather than telling them they have a S1+S2 string...
HarryDC The core of the problem statement says 'Your challenge is to help him find the minimum number of characters of the first string he needs to change to make it an anagram of the second string'. This does not imply the require reshuffling of the string. For example changing this to: Your challenge is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string. Would make things clearer without giving away too much.
hydra_smith Agreed, the original one is kind of confusing.
dheeraj I've made this change! Thanks for notifying us!
particle Doesn't it follow from the definition of an anagram?
bramyers [deleted]
tao_zhang My java solution:
import java.util.*; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t-->0){ String str = sc.next(); int len = str.length(), count = 0; if (len%2!=0){ System.out.println(-1); continue; } String s1 = str.substring(0,len/2); String s2 = str.substring(len/2,len); char[] s1Chars = s1.toCharArray(); for (char c : s1Chars){ int index = s2.indexOf(c); if (index == -1){ count++; } else { s2 = s2.substring(0,index)+s2.substring(index+1); } } System.out.println(count); } } }
mithildeeva awesome! such simple logic. Thankyou!
adikiit123 Will it work with the string bbxxxaxb ?
humoyun_ahmad core of this solution is indexOf() method
tvucic1 Beautiful!!
Gurparshad amazing , very helpful
varlyanijatin88 Solution is Amazing. But can you tell me why did you added
s2.substring(index+1);Thanks in advance.
ritikagarwal what does while (t-->0) means in above programs
palashmax Fun question: How do you fail TestCase #0 when you have already passed it? Isn't it the same as in the question or the one you use to check your solution(Run code)?
kumarjivi Same issue with me, When I submit the code it says almost all cases fail, including test Case#1. You got solution for this?
tilper Test case #1 is the same as the sample for this problem.
hugo_ratiney I pass only #1 and #14... You can get almost the same score with :
print("3\n1\n-1\n2\n0\n1\n")
sushilll [deleted]motwanirushil wrong
fcampinho C# code using dictionary
int t = Convert.ToInt32(Console.ReadLine()); //int t = 1;
for (int a0 = 0; a0 < t; a0++) { string s = Console.ReadLine(); if (s.Length % 2 != 0) { Console.WriteLine(-1); continue; } Dictionary<char, int> l = new Dictionary<char, int>(); int half = s.Length / 2; for (int i = 0; i < half; i++) { if (i < half) { if (l.ContainsKey(s[i])) l[s[i]]++; else l.Add(s[i], 1); } } int qtyDiff = 0; for (int j = half; j < s.Length; j++) { if (l.ContainsKey(s[j]) && l[s[j]] > 0) l[s[j]]--; else qtyDiff++; } Console.WriteLine(qtyDiff); }
simonzhu91 Interesting... I did it the other way: By checking the number of elements in the dictionary after the 2nd for loop, as opposed to counting the number of elements in the 2nd string that the dictionary does not contain.
Also, I tried to experiment with a 1 loop solution, ie: count the total number of characters in the entire string, and count the number of odd occurences and divide that by 2. But that does not seem to work :(
DIVYANSHUCEG C solution
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t,x; scanf("%d",&t); for(x=0;x<t;x++) { int first[26]={0},second[26]={0}; int count=0; char str[10000]; scanf("%s",str); int i,k=strlen(str)-1; if(strlen(str)%2==1) count=-1; else { i=0; while(i<strlen(str)/2) { first[str[i++]-'a']++; second[str[k--]-'a']++; } for(i=0;i<26;i++) { if(first[i]>second[i]&&first[i]!=0) count+=abs(first[i]-second[i]); } } printf("%d\n",count); } return 0;}
udayshankar911 int diff = 0,t; t = s.nextInt(); String str = s.next(); int len = str.length(); for(int k = 0; k < t;k++) { if(len%2!=0) System.out.println("-1"); else { String str1 = str.substring(0,(len/2)); String str2 = str.substring(len/2); for(int i=0;i<str1.length();i++) { if(!str2.contains(str1.charAt(i)+"")) diff++; } System.out.println(diff); } }udayshankar911 Guys TC 1 an 14 executed but others failed. when i tested in Netbeans IDE i dont find any prob. can anyone look at it and leem know the issue .
DanLuo if there is 2 "a" in str1, but only 1 "a" in str2, diff will not increase
cherry_9 can you please explain this further
omtonape take second string into stringbuilder and if char from first string is present in second string remove char at that position from stringbuilder if char is not present in second string then increment count final answer is count.... thanks DanLuo
mayurnagdev123 I did something similar.Converted String to StringBuffers sb1 and sb2. Upon iterating characters through sb1: if the character is found in sb2,then change that character value in sb2 to some other value(say '/') so that it couldn't be found in further iterations. This is essential as sb1 may have repeating characters.
sivach Use stringbuilder for first string, remove the char from builder if exist and at the end, answer = string builder length.
udayshankar911 Got it. thnq :)
dsaxena I understood the problem in your code but I a, little bit confused about the mentioned solution. actually I am not much familier with Java, I am currently learning, So can you please explain me the solution??
omtonape but in that case also mine are passing test cases 1 and 14 but rest are failing
andadeacu static int anagram(String s) { int result = 0; Map map = new HashMap();
if (s.length() % 2 != 0) { return -1; } else { int half = s.length() / 2; for (int k = 0; k < half; k++) { char letter = s.charAt(k); if (!map.containsKey(letter)) { map.put(letter, 1); } else { Integer frequency = map.get(letter); map.put(letter, ++frequency); } } for (Map.Entry<Character, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " " + entry.getValue()); } for (int k = half; k < s.length(); k++) { char letter = s.charAt(k); //System.out.println("a doua jumatate este:"); //System.out.println(letter); if (!map.containsKey(letter)) { result++; } else { Integer freq = map.get(letter); freq--; map.put(letter, freq); } } for (Map.Entry<Character, Integer> entry : map.entrySet()) { System.out.println(entry.getKey() + " " + entry.getValue()); } return result; } }for String xaxbbbxx I obtain 0.
Can someone one say me why?
19soumikrakshi96 you should take the string input inside the testcase loop.
13h61a05f3 Your code don't work for input aabacb
deepa_navaneeth The last test case fails. Try with xaxbbbxx.
iainws I failed with c++ because of map.count(element). when the element count is 0, it still registers as a hit. Somewhat confusing if you choose to use this language reference. its better to check with if(map.count(element) && map.count(element) != 0). good problem.
shaik_jabivulla its not full solution
mayurnagdev123 This wont work for: "fdhlvosfpafhalll" which is the input string in the first test case
knaman1009 Plz send the modified code
anuj19 If your if condition is first[i] >second[i] then what is the need to use abs func ?
saravanakumars first[str[i++]-'a']++; what happen in this step i dont understand can u please help
DIVYANSHUCEG converting the characters in the range of 0-26 because my array size is 26.
SHUBH778 So basically solution will be located at different positions ,so how did you go through it
rwan7727 C++:
int q; cin >> q; for(int a0 = 0; a0 < q; a0++){ string s; cin >> s; if (s.length()%2) cout << -1 << endl; else { vector <int> s1(26); vector <int> s2(26); for (int i=0;i<s.length()/2;i++) { s1[s[i]-'a']++; s2[s[i+s.length()/2]-'a']++; } int min=0; for (int i=0;i<26;i++) if (s2[i]>s1[i]) min+=(s2[i]-s1[i]); cout << min << endl; } }ishujain18123 include
include
using namespace std; int main() {int t; char s[100000]; cin>>t; for(int i=1;i<=t;i++) {cin>>s; int coun=0,l=strlen(s); if(l%2==1){cout<<"-1"<
} cout<
}
}
what is wrong with this code?
hh170031061 abs was not described in the scope. please tell the meaning of that line.
malawadkarrahul [deleted]malawadkarrahul You have not included the header file which includes the library function abs!! Which is cmath or math.h
s05_31468 can you explain the last if condition
akshar36 Really nice code..but why first[i]>second[i] .. i couldnt understand that part.. can you explain :)
2019201057_anur can you explain how did you calculate count
jake_griffin That doesn't work because of something like "aabb". Both characters need to change, but your solution would find that there are an even number of each, so nothing needs to change. If you increment the character counts for the first half of the string and decrement for the second half, then discard the negatives and sum the positives, I think that would work.
souravsachdeva [deleted]souravsachdeva [deleted]souravsachdeva [deleted]souravsachdeva [deleted]raviloga316 What is this "&& l[s[j]] > 0" for?
sungmkim80 It seems like my C# solution is sloppier compared to this dictionary version... I am removing each character that doesn't match. Removing would decrease the length, that's where "i--" comes into play in my code.
private static int GetChangeCountForAnagram2(string testCase) { if (IsLengthOdd(testCase)) return NOT_POSSIBLE; // Parse test case for left and right texts int middleIndex = testCase.Length / 2; var left = testCase.Substring(0, middleIndex); var right = testCase.Substring(middleIndex); int total = 0; for (int i = 0; i < right.Length; i++) { var c = right[i]; int index = left.IndexOf(c); if (index < 0) { right = right.Remove(i, 1); total++; } else { left = left.Remove(index, 1); right = right.Remove(i, 1); } i--; } return total; }
juanmf java by counting: https://www.hackerrank.com/challenges/anagram/forum/comments/314333
Rishabh094 int anagram(string s){ vector<int> count(26,0); if(s.length()%2==0){ for(int i=0;i<s.size()/2;i++){ count[s[i]-'a']++; } for(int i=s.size()/2;i<s.size();i++){ count[s[i]-'a']--; } int sum = 0; for(int i=0;i<26;i++){ sum += abs(count[i]); } return sum/2; } else return -1; }
yinqiankong clear solution.
gkeswani92 Python 3 solution:
from collections import Counter for _ in range(int(input())): s = input() l = len(s) if l % 2 == 1: print(-1) else: count = 0 s1, s2 = Counter(s[:l//2]), Counter(s[l//2:]) for char in s2: current = s2[char] - s1.get(char,0) if current > 0: count += current print(count)particle I did too. This is supposed to be O(n) right?
particle If you want to utilize the Counter you can do (Counter(s1) - Counter(s2)).elements() this returns an iterator. So either convert to list then sum or use sum(1 for _ in iterator).
jellybeanfiend You can also do (Counter(s1) - Counter(s2)).values() to get the list of counts outright. Not a big difference but at least you can skip the step of converting to a list :)
hutcho66 Yep. A simple
print(sum((Counter(s[:l//2]) - Counter(s[l//2:])).values()))works (after checking the length is even of course). No loop!
lunatic13 can u please explain the use of counter?
m_a_r_c_e_li_n_o Take a look at the C example below by "etayluz", followed by my explanation on why the counter is reduced by half at the end. It might help shed some light as to why a counter is used to solve the problem.
etayluz C Solution:
int main() { int t; scanf("%d", &t); while (t--) { char s[10000]; scanf("%s", s); int len = strlen(s); if (len % 2 == 1) { printf("-1\n"); continue; } int letter[26] = {0}; int count = 0; for (int i = 0; i < len/2; i++) { char c = s[i]; letter[c - 'a']++; } for (int i = len/2; i < len; i++) { char c = s[i]; letter[c - 'a']--; } for (int i = 0; i < 26; i++) { count += abs(letter[i]); } printf("%d\n", count/2); } return 0;}
yrelhan4 I am kinda having trouble understanding the count/2 part. An explanation would be good. Thanks.
m_a_r_c_e_li_n_o This method counts for differences on both strings, so the answer needs to be reduced by half since the question asks how many times ONE string needs to be modified to match the other. For example, with string "aaabbb", this method concludes that "aaa" doesn't match "bbb" and that "bbb" doesn't match "aaa", implying that 6 letters need to be modified for them to equal somehow (i.e. cccccc). However we just need one string to transform into another, so really only 3 letters need to be modified (i.e. "aaa" from first string becomes "bbb", thus matching the second).
Joker8 Instead of checking both first and second string. I checked only the first string and then didn't multiply the count by half.
brokenmystery used the exact same logic already. The small difference being i used letter2 for 2nd for loop and then calculated the difference
aquio Same idea in Swift times out in some of the test cases. Any optimization suggestions?
var t = Int(readLine()!)! for _ in (0..<t) { var strArr = readLine()!.characters.map{String($0)} if strArr.count % 2 != 0 { print("-1") } else { var middle = strArr.count / 2 var map = [String : Int]() for i in (0..<middle) { if map[strArr[i]] == nil { map[strArr[i]] = 1 } else { map[strArr[i]] = map[strArr[i]]! + 1 } if map[strArr[middle + i]] == nil { map[strArr[middle + i]] = -1 } else { map[strArr[middle + i]] = map[strArr[middle + i]]! - 1 } } var res = 0 for (key, value) in map { res = res + abs(value) } print(String(res/2)) } }
peterkirby You could translate the logic more directly by using .utf8 on a string to get the ASCII codes, subtracting the ASCII value of 'a' (97), and using that to index an array of size 26 representing the letters and their counts (like the C/C++ examples posted here). It's possible that using the map and indexing it with strings is more expensive than doing that.
aquio Your suggestion has been really helpful! As you suggested, indexing a simple frequency array instead of a map results in better performance. Thanx!
Here is the working version for Swift:
var t = Int(readLine()!)! for _ in (0..<t) { var strArr = Array(readLine()!.characters) if strArr.count % 2 != 0 { print("-1") continue } var letter = [Int](count: 26, repeatedValue: 0) var count = 0 for i in (0..<strArr.count / 2) { var charNum = Int(Array(String(strArr[i]).utf8)[0]) letter[charNum - 97] = letter[charNum - 97] + 1 } for i in (strArr.count / 2..<strArr.count) { var charNum = Int(Array(String(strArr[i]).utf8)[0]) letter[charNum - 97] = letter[charNum - 97] - 1 } for i in (0..<26) { count = count + abs(letter[i]) } print(String(count / 2)) }
Sasintheran can you please explain the term...
letter[c-'a']++;
I can't understand this line...how its works? explain me please...
aquio letter is a frequency array - you count how many appearances of each letter of alphabet are there in your string. So, at letter[0] you have frequency for 'a', at letter[1] for 'b' etc. For example, if your c within the loop at some point is 'd', then 'd' - 'a' = 100 - 97 = 3, (100 and 97 are respective character codes) and you do required operation on letter[3]
arturs_aksjonen1 Fails at test case #8 (as of 07.2019) with 'wrong answer' like my own solution ;) I run all test cases within case #8 but with no luck.
lose311 This worked for me:
from collections import Counter n = int(input()) for _ in range(n): test = input() length = len(test) if len(test) % 2 != 0: print("-1") else: s1 = Counter(test[:length//2]) s2 = Counter(test[length//2:]) diff = s1 - s2 print(sum(diff.values()))peterkirby C++ Solution
void countLetters(vector<int> &letters, string s, int begin, int end) { for (int i = begin; i < end; ++i) ++letters[s[i] - 'a']; } int numChanges(const string &s) { int length = s.length(); if (length % 2) // odd return -1; int half = length / 2; vector<int> v1(26, 0), v2(26, 0), results(26, 0); countLetters(v1, s, 0, half); countLetters(v2, s, half, length); transform (v1.begin(), v1.end(), v2.begin(), results.begin(), [](int x, int y) { return abs(x - y); }); int sum = accumulate(results.begin(), results.end(), 0); return sum / 2; }
Nicke My solution in C#, 100% pass.
static int anagram(string s) { if (s.Length % 2 != 0) return -1; string a = s.Substring(0, s.Length / 2); string b = s.Substring(s.Length / 2); foreach(char c in b) { if (a.IndexOf(c) > -1) a = a.Remove(a.IndexOf(c), 1); } return a.Length; }
Day_dreamer int main() { int t; cin>>t; while(t--){ string s; cin>>s; int n = s.size(); if(n%2!=0) cout<<-1<<endl; else{ int sum = 0; int arr1[26] = {0}; for(int i=0;i<(n/2);i++){ arr1[s[i]-'a']++; } for(int i=(n/2);i<n;i++){ arr1[s[i]-'a']--; } for(int i=0;i<26;i++){ if(arr1[i]>0) sum = sum+arr1[i]; } cout<<sum<<endl;} } return 0; }
revengeCoder Easy to understand Java solution. Works for all test cases.
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); scan.nextLine(); for (int i = 0; i<t; i++){ String str = scan.nextLine(); int[] lettersArray = new int[26]; int changes = 0; if (str.length() % 2 == 0){ for (int j = 0; j<str.length()/2; j++){ lettersArray[str.charAt(j)-'a']++; } for (int j = str.length()/2; j<str.length(); j++){ if(lettersArray[str.charAt(j)-'a'] > 0) lettersArray[str.charAt(j)-'a']--; } for (int j = 0; j<26; j++){ changes += lettersArray[j]; } System.out.println(changes); } else{ System.out.println(-1); } } }
Sort 465 Discussions, By:
Please Login in order to post a comment