isPalindrome3 - Crack Coding Interviews

So far we have talked about two ways of solving these problems. Now let's talk about solution number three. This is kind of similar to what we had in solution one. But let me first remove everything here. But instead of building a frequency table or an array of Booleans to store the... to toggle the Boolean value in each position, we're going to be using a what we call integer bit vector. So instead of having a Boolean array, we're going to have basically an integer of zero that has about 26 positions. And so each position will be representing one letter, right? So first we're going to need 26. So that's 5, 5, 5, 5, 5. That's 26. So what we're going to do is whenever we encounter a letter, for example, a letter C, right? So a letter C is two letters away from letter A. So letter C minus letter A is 2. So previously in the first solution, we're going to be basically toggling the position 2 Boolean value from a false to true. So here we're going to be basically toggling the second position here in the bit vector from a 0 to 1. And by toggling, I mean if it appeared twice, right? So let me first toggle the second position to be 1, right? So and if it's the second time I'm encountering the same character C, I'm still going to toggle this. So if it's already a 1, so this time it's going to be a 0. So this is going to be switching between 1 and 0 all the time. But think about it now. If we have even number of letter Cs, so at the end, this is always going to be 0, right? So with that being said, at the end, if we want to have no more than one odd number of letters, we only have to check the final result in the bit vector that we have one. We cannot have more than one 1s in this bit vector, right? So let's see how do we implement that. All right. So first of all, let's talk about how do we toggle a vector, right? So a bit vector. So let's call this function integer. And this is going to take an input to bit vector, which is going to be integer. I'm just going to call it a input. And I'm going to pass in a index argument. And this index will be the position number which we have to toggle, right? And so just think about it. How do we toggle this? First, we're going to be needing what we call a mask. What this mask is going to do is it's going to create a new bit vector. And this vector at the position index is going to hold a value of 1. And the rest of the values are all 0s. So in order to achieve that, we're going to use a bit operator in Java. That's called a left shift. And so we're going to be basically shifting the number 1 indexed number of times to the left. So what that means is, say, I'm going to start with the number 1, right? So that's my target. So say if I have 1, and that's the integer. That's the integer 1. And if the index is equal to, for example, 3. So I'm going to be shifting the 1 three times to the left. So 1, 2, and 3. So it's going to reach this point, right? That's what it means. And just think about it. If we already have an integer of all 0s, how do we toggle this bit here, right? So there's the bit operator called XOR. Or in Java, it's this operator. So if we do XOR, what XOR means is that if the two bits are different, it's going to be 1. And if the two bits are the same, it's going to return 0. So 1 XOR 1 is equal to 0. But 0 XOR 1 is equal to 1. But 0 XOR 0, because they're the same, is still going to be 0. So it returns 1 only if the two bits are different. And this way, we can use this logic to toggle this one right here. So basically, we shift this number of times to the left. And then we're going to do a XOR. So input is equal to input XOR mask. And this notation can be simplified as input XOR equals mask. So essentially, they're the same thing. So I'm just going to do the simplified version. And we're going to return the input. So this way, we take in the input integer. And we can toggle the position index of the input vector, okay? All right. So we have the toggle function ready for us. So the next thing we're going to have to do is creating the bit vector. So let's just call this create bit vector, okay? So this is going to take the input of string, okay? So this is where the real logic lies in. So we're going to have to do a for loop. We're going to loop through each character in the string input. So two character array, okay? And for each character, we're going to be first of all, calculating the index is equal to C minus A, okay? So here we have the index of this. It's kind of similar to the index of the Boolean table that we use in solution number one. And next, what we're going to do is we're going to be toggling the bit value at position index. So first of all, we have a declared bit vector, which is going to be all zeros. So we're going to say bit vector is equal to toggle repassing the bit vector itself and index, okay? After we're toggling this, and we're going to be looping through each and every one of those. And finally, we're going to return the bit vector. So at this point, we expect if it's a permutation of palindrome, this bit vector integer has no more than one number one, okay? So it has no more than one ones. So we're going to write our main function here is palindrome string input. And we're going to first get the bit vector from this input. So it's going to be integer. Bit vector is equal to create bit vector and takes in input as an argument, okay? And then we're going to check if this vector has no more than one ones. How do we do that? Let's think about this for a moment. Say if I have a bit vector of 000100, think about this example, okay? I have only one one in this bit vector. And if I were to subtract one from this one here, what would I get? I'm going to be getting 00000 because I'm subtracting one. There's a binary operation, so 011, right? And this time, if I'm going to do an AND operation on these two, what am I getting? I'm going to be getting all zeros, right? So that's a trick that we can use. So subtract one from the bit vector and do an AND operation, and we should be getting a zero. If there's no more than one ones in the bit vector. So let's do that. So the Boolean, I'm going to say just say retar bit vector AND bit vector minus one. So let's copy and paste this into IDE and see if it's working. I'm going to be using IntelliJ again. First off, let's remove everything here. Oh, I'm sorry. Is the SQL true? Oh, I need to put one more parenthesis here. Okay, there we go. All right, so let's make everything static so that we can call it directly. Static, static, and static. So all right, let's go ahead and run this. Again, we're getting true, true, and false. So let's talk about the time complexity again of this algorithm. Again, we have to do a for loop to loop through each one of them in order to toggle the bit value at that position. So again, the time complexity will be a big O of N.