boolean isPalindrome(String s){
if(s.length() == 0) return true;
if(s.length() == 1) return true;
char[] sa = s.toCharArray();
Stack<Character> stk = new Stack<>();
for(int i = 0; i < sa.length/2; i++){
stk.add(sa[i]);
}
int rightSideStart = sa.length/2;
if(sa.length % 2 != 0) rightSideStart++;
for(int i = rightSideStart; i < sa.length; i++){
if(stk.pop() != sa[i]) return false;
}
return true;
}