isPalindrome2 - Crack Coding Interviews

Now let's talk about another way of solving this problem. So previously we talked about building a frequency table to store the number of occurrences for each character in the input string and then loop through the frequency table and see how many odd numbers we have. We talked about we cannot have more than one odd number in the frequency table for the input string to be a permutation of a palindrome. So now let's explore what else we can do to solve this problem. Now instead of looping through the frequency table to look for the number of odd numbers we can pretty much implement a counter that counts the number of odd numbers in the frequency table. So let's see how to implement that. So first I'm going to delete these solutions from last time. So first of all we still need a frequency table. So once we have the frequency table what we can do is, you know what, I think we can pretty much combine these two together because we're looping through the character array anyway. So I'm going to move these couple lines of code from here to here. And then I don't need this anymore. All right. So while we're looping through the string input, first we increment the counter so that we have the number of occurrences for each character as we go. So after we implement the counter we can say if this counter here, right, so if this counter is an odd number not 2 is equal to 1. If it's an odd number then we're going to be incrementing a counter. Let's just call this countOdd, incrementing this counter here. And first of all we have to define a counter on countOdd. Initialize it to 0. All right. So every time we encounter an odd number after the increment we're going to increment this counter. And if it's an odd number, sorry, if it's an even number else we're going to be decrementing this counter. Right. So basically what this does is it keeps track of the number of odd numbers in this frequency table. Right. So I remember that we do need no more than one odd number. So at the end, after everything, this value, if the input value is a permutation of the palindrome, this number should be no more than 1. So basically we're going to say this number cannot be more than 1, less than or equal to 1. Okay. It's a little bit different from the first one but I wouldn't call this even an improvement in terms of time complexity because we do have to execute a couple more lines for each letter where previously we're only basically updating the frequency table and make a comparison against whether it's even or odd. Right. But here we're doing a few more operations here. So the time complexity is still a big O of n. But, you know, you can argue that it's cleaner, you can talk with your interviewers, this is just another approach that we can solve this problem.