Amazon Interview Question Java Developers
Country: United States
Interview Type: Written Test
I am trying to write a function which takes as input an array of strings with only lower case letters. Function returns an array of same strings but with each string has its letter rearranged such that it becomes a palindrome if possible, and if not then it returns -1.
public static Object buildPalin(String[] arrayOfStrings)
{
String[] palindrome = new String[arrayOfStrings.length];
int offset = 0;
int charWithoutReflection = 0;
List<String> whole= Arrays.asList(arrayOfStrings);
String wholeString = String.join("", whole);
for(int i=0; i< arrayOfStrings.length; i++)
{
if (arrayOfStrings[i] != "")
{
int currentCharPosition = wholeString.indexOf(arrayOfStrings[i],
i + 1);
if (currentCharPosition != -1)
{
palindrome[offset] = arrayOfStrings[i];
palindrome[palindrome.length - 1 - offset] =
arrayOfStrings[i];
arrayOfStrings[currentCharPosition] = "";
arrayOfStrings[i] = "";
}
else {
if (charWithoutReflection > 0)
return -1;
palindrome[palindrome.length/2] = arrayOfStrings[i];
charWithoutReflection++;
}
offset++;
}
}
return palindrome;
}
This function works fine for case when input array is like this
{"a", "b", "a"}
{"a","b","c"} and so on.
but when i am having input like below:
{"aba", "bb", "cac"} and like this that is array of strings it fails.
Any guidance or suggestion on this is helpful.
I came out with this solution, it is O(2*n), first you traverse every string to know how many occurrence of every character from ‘a' to ‘z’, then you compose the palindrome. Since there is no rule to compose the palindrome I’m supposing alphabetical order. For example string: “rrrraaffttt" will return “afrrtttrrfa”.
Test these lines:
char *strings[] = {"ddd", "deeee", "weee", "fjff", "rrrraaffttt"};
int size = sizeof(strings)/sizeof(char*);
palindromes(strings, size);
char * palindrome (char *string) {
size_t size = strlen(string);
if (size < 2) {
return string;
}
int buffer[26];
std::fill(buffer, buffer+26, 0);
for (int i=0; i<size; i++) {
buffer[string[i] - 'a'] += 1;
}
char * output = new char [size];
std::fill(output, output+size, '0');
bool flag = false;
int k = 0;
for (int i=0; i<26; i++) {
int count = buffer[i];
if (count > 0) {
if ((count%2 == 1 && size%2 == 0) ||
(count%2 == 1 && flag)) {
output[0] = '-';
output[1] = '1';
output[2] = '\0';
break;
} else {
if (count & 1) {
output[size/2] = 'a' + i;
flag = true;
}
for (int j=0; j<(count/2); j++) {
output[k++] = 'a' + i;
output[size-k] = 'a' + i;
}
}
}
}
return output;
}
void palindromes (char *strings[], size_t size) {
for (int i = 0; i<size; i++) {
strings[i] = palindrome(strings[i]);
}
}
To know if a given set of characters can form a palindrome string
1. Sort the characters.
2. In a palindrome string, every character will have at least one duplicate. A palindrome string can be of odd length which means that there can be one character without any duplicate.
3. Check if the input string satisfies point 2 (it becomes easy to check after sorting).
4. If yes, form a palindrome string. Repeat the process for all string in the array.
private static List<String> makePalindromeOfAll(List<String> strings) {
List<String> palindromeStrings = new ArrayList<String>();
for (String string : strings) {
if (string == null || string.isEmpty()) {
palindromeStrings.add(string);
continue;
} else {
if (makePalindrome(string) == null) {
return null;
} else {
palindromeStrings.add(string);
}
}
}
return palindromeStrings;
}
public static String makePalindrome(String string) {
if(string == null || string.isEmpty()) {
return string;
}
if(string.length() == 1) {
return string;
}
char[] characters = string.toCharArray();
Arrays.sort(characters);
int uniqueCharacterCount = 0;
int oddCharacterIndex = 0;
if(characters.length % 2 == 0) {
for(int i = 0; i < characters.length; i+=2) {
if(characters[i] != characters[i+1]) {
return null; // not a palindrome
}
}
} else {
for(int i = 0; i < characters.length; i+=2) {
if(characters[i] != characters[i+1] && uniqueCharacterCount < 1) {
if(characters.length >= i+2 && characters[i+1] == characters[i+2]) {
oddCharacterIndex = i;
} else {
oddCharacterIndex = i+1;
}
i--;
uniqueCharacterCount++;
}
if(uniqueCharacterCount > 1) {
return null;
}
}
}
//now, make a palindrome string
StringBuilder sb = new StringBuilder(String.copyValueOf(characters));
if(characters.length % 2 == 0) {
return sb.replace(sb.length()/2, sb.length(), new StringBuilder(sb.substring(sb.length()/2)).reverse().toString()).toString();
} else {
char oddCharacter = sb.charAt(oddCharacterIndex);
sb.deleteCharAt(oddCharacterIndex);
sb.replace(sb.length()/2, sb.length(), new StringBuilder(sb.substring(sb.length()/2)).reverse().toString());
sb.insert(sb.length()/2, oddCharacter);
return sb.toString();
}
}
for (int i = 0; i < listOfStrings.Length; i++)
{
string result = Palindrome(listOfStrings[i]);
Console.WriteLine("Input:{0}, result:{1}", listOfStrings[i], result);
listOfStrings[i] = result;
}
private string Palindrome(string s)
{
int[] listOfChars = new int[26];
//Default values should set to zero, this is not mandatory; try running by commenting this one
//for (int i = 0; i < 26; i++)
//{
// listOfChars[i] = 0;
//}
int totalChars = 0;
foreach (char c in s)
{
++listOfChars[c - 'a'];
totalChars++;
}
int oddOccurances = 0;
int oddOccuranceLocaton = -1;
for (int i = 0; i < 26; i++)
{
if (listOfChars[i] % 2 != 0)
{
++oddOccurances;
oddOccuranceLocaton = i;
}
}
if (totalChars % 2 == 0 && oddOccurances > 0)
{
//Even number length, char with odd number of occurances is not a palindrome
return "-1";
}
else if (oddOccurances > 1)
{
//odd lenth, there should be only one char with odd number of occurances
return "-1";
}
else
{
//return palindrome, this can be optimized
int start = 0;
int end = totalChars - 1;
char[] result = new char[totalChars];
for (int i = 0; i < 26; i++)
{
if (oddOccuranceLocaton == i)
{
continue;
}
for (int j = 0; j < listOfChars[i]/2; j++)
{
result[start++] = (char)(i + 'a');
result[end--] = (char)(i + 'a');
}
}
if (oddOccuranceLocaton != -1)
{
for (int j = 0; j < listOfChars[oddOccuranceLocaton]; j++)
{
result[start++] = (char)(oddOccuranceLocaton + 'a');
}
}
return new string(result);
}
here is my C# version of solution. i think we can not build palindrome string if we get more than one char with odd occurrence
following will be steps to solve it
1 iterate string array and find char & it occurrence count
2 loop above dictionary & build string start part & end part . if we get more than one char having odd occurrence retrun -1
private static void Main(string[] args)
{
var inputList = new List<string>();
inputList.Add("rrrraaffttt");
inputList.Add("rrraaffttt");
var result= Palindrome(inputList );
Console.WriteLine("Palindrome is {0} ", result);
Console.ReadLine();
}
private static Dictionary<char, int> FindOccurrenceOfChar(IEnumerable<string> args)
{
var charOccurrenceCnt = new Dictionary<char, int>();
foreach (var inputChar in args.SelectMany(inputString => inputString))
{
if (charOccurrenceCnt.ContainsKey(inputChar))
charOccurrenceCnt[inputChar]++;
else
charOccurrenceCnt.Add(inputChar,1);
}
return charOccurrenceCnt;
}
private static string Palindrome(IEnumerable<string> args)
{
string beginingPart = String.Empty;
string endPart = String.Empty;
string middlePart = String.Empty;
var charOccrCount = FindOccurrenceOfChar(args);
var charEnumerator = charOccrCount.GetEnumerator();
while (charEnumerator.MoveNext())
{
int reminder = 0;
int loopCount = Math.DivRem(charEnumerator.Current.Value, 2, out reminder);
if (reminder == 0)
{
for (int index = 0; index < loopCount; index++)
{
beginingPart += charEnumerator.Current.Key;
endPart = charEnumerator.Current.Key + endPart;
}
}
else if (string.IsNullOrEmpty(middlePart))
{
middlePart =new string(charEnumerator.Current.Key,charEnumerator.Current.Value);
}
else return "-1"; // for sure if we get more than 1 char having odd Occurrence . we will not able to build Palindrome string
}
return beginingPart + middlePart + endPart;
}
Java Streams makes it easy to check that at most one character appears an odd number of times
public class Palindrome {
public static void main(String[] args) {
String word = "ghijjihkkgg";
String[] split = word.split("");
Arrays.sort(split);
Map<String, Integer> result = Arrays.stream(split)
.collect(Collectors.groupingBy((String s) -> s))
.values().stream()
.collect(Collectors.toMap((list) -> (String) list.get(0), (list) -> list.size()));
if (result.values().stream().filter(i -> (i & 0x1) == 1).count() > 1) {
System.out.println("No palindrome ");
} else {
StringBuffer prefix = new StringBuffer();
String center = "";
for (Map.Entry<String, Integer> e : result.entrySet()) {
String c = e.getKey();
for (int i = 0; i < e.getValue() / 2; i++) {
prefix.append(c);
}
if ((e.getValue() & 0x1) == 1) {
center = c;
}
}
StringBuffer palindrome = new StringBuffer().append(prefix).append(center);
prefix.reverse();
palindrome.append(prefix);
System.out.println("Palindrome of " + word + " is " + palindrome);
}
}
}
static ArrayList<String> arr = new ArrayList<>();
public static void palidrome() throws IOException {
InputStream fis = new FileInputStream("C://tmp/palidrome.txt");
InputStreamReader isr = new InputStreamReader(fis, Charset.forName("UTF-8"));
BufferedReader br = new BufferedReader(isr);
String line;
while ((line = br.readLine()) != null) arr.add(line);
for (int i=0; i<arr.size(); i++) {
if (!isPal(arr.get(i))) arr.set(i, "-1");
System.out.println(arr.get(i));
}
}
public static boolean isPal(String str) {
int i=0; int k = str.length()-1;
while (i<=k) {
if (str.charAt(i)==str.charAt(k) ) {
i++;
k--;
}
else return false;
}
return true;
}
static ArrayList<String> arr = new ArrayList<>();
public static void palidrome() throws IOException {
InputStream fis = new FileInputStream("C://tmp/palidrome.txt");
InputStreamReader isr = new InputStreamReader(fis, Charset.forName("UTF-8"));
BufferedReader br = new BufferedReader(isr);
String line;
while ((line = br.readLine()) != null) arr.add(line);
for (int i=0; i<arr.size(); i++) {
if (!isPal(arr.get(i))) arr.set(i, "-1");
System.out.println(arr.get(i));
}
}
public static boolean isPal(String str) {
int i=0; int k = str.length()-1;
while (i<=k) {
if (str.charAt(i)==str.charAt(k) ) {
i++;
k--;
}
else return false;
}
return true;
}
import java.util.*;
public class Solution {
private static String makePalindromeOfAll(String string) {
String palindromeString = "";
if (string.isEmpty()) {
return null;
}
return makePalindrome(string);
}
public static String makePalindrome(String string) {
if(string.length() == 1) {
return string;
}
char[] characters = string.toCharArray();
Arrays.sort(characters);
StringBuffer startString = new StringBuffer();
StringBuffer endString = new StringBuffer();
int uniqueCharacterCount = 0;
int oddCharacterIndex = 0;
if(characters.length % 2 == 0) {
for(int i = 0; i < characters.length; i+=2) {
if (characters[i] != characters[i + 1]) {
return null; // not a palindrome
}
startString.append(characters[i]);
endString.append(characters[i + 1]);
}
return startString.append(endString.reverse()).toString();
}
else {
for(int i = 0; i < characters.length; i+=2) {
if(characters[i] != characters[i+1]) {
oddCharacterIndex = i;
i--;
uniqueCharacterCount++;
}
else {
startString.append(characters[i]);
endString.append(characters[i + 1]);
}
if(uniqueCharacterCount > 1) {
return null;
}
}
}
//now, make a palindrome string
StringBuilder sb = new StringBuilder();
sb.append(startString);
sb.append(String.valueOf(characters[oddCharacterIndex]));
sb.append(endString.reverse());
return sb.toString();
}
public static void main(String args[] ) throws Exception {
Scanner scanner = new Scanner(System.in);
List<String> stringList = new ArrayList<>();
int i = 0;
while(i < 1)
{
System.out.print("Enter string: " );
stringList.add(scanner.next());
i++;
}
String newString = makePalindromeOfAll(stringList.get(0));
System.out.println(newString);
}
}
public class Palindrome {
public static void main(String []args){
getPalindrome(args);
}
public static String[] getPalindrome(String []args){
Set<String> dictionary = createDictionary();
List<String> palindromes = new ArrayList<>();
for (String word: args)
for (String combination : getCombinations(word))
if (! combination.equals(word))
if (dictionary.contains(combination)){
palindromes.add(combination);
System.out.println(combination);
}
if (palindromes.size() < 1)
System.exit(-1);
return palindromes.toArray(new String[palindromes.size()]);
}
private static Set<String> createDictionary() {
Set<String> dictionary = new HashSet<>();
dictionary.add("art");
dictionary.add("tar");
dictionary.add("rat");
return dictionary;
}
private static List<String> getCombinations(String word) {
List<String> combinations = new ArrayList<>();
if (word.length() <= 1)
return combinations;
if (word.length() == 2)
{ combinations.add(word);
combinations.add( exchg(word));
return combinations;
}
for (int i = 0; i < word.length(); i++)
{
String first = word.substring(0, i);//
String second = word.substring(i+1,word.length());// rt
for (String firstAndSecond: getCombinations( first + second) )
combinations.add(word.charAt(i) + firstAndSecond);
}
return combinations;
}
private static String exchg(String word){
return ""+ word.charAt(1) + word.charAt(0);
}
}
This is a function that converts an array of strings all in lower case to palindrome, it relies on a dictionary. The complexity is O(nm) where n is the number of words and m is the average word length. The dictionary should be in lowercase and should also contain multi-word combinations with apostrophe without the apostrophe. At the end a map for multi-words without apostrophe should be mapped to separate words with apostrophe.
public class Palindrome {
static Set<String> dictionary;
public static void main (String []args){
dictionary = createDictionary();
args = getPalindrome(args);
for (String string : args) {
System.out.println(" "+ string);
}
}
private static String[] getPalindrome(String[] args) {
for (String string : args) {
char[] reversed = reverse(string);
StringBuilder buffer = new StringBuilder();
StringBuilder newWord = new StringBuilder();
for (int i=0; i< reversed.length; i++){
// ignore spaces
if (reversed[i]!=' '){
newWord.append(reversed[i]);
//Dictionary must be in lowercase
if (isInDictionary(newWord.toString())){
// if words needed in strict correct lowercase and uppercase combination then hashmap to map lowercase to upperLowercase word
// add spaces when needed
buffer.append(newWord).append(" ");
newWord = new StringBuilder();
}
}
}
string = buffer.toString();
if (string.equals("")) System.exit(-1);
}
return args;
}
private static boolean isInDictionary(String word) {
return (dictionary.contains(word));
}
private static char[] reverse(String string) {
char [] stringAr = string.toCharArray();
int length = stringAr.length;
if (length > 1)
for (int i=0; i < length /2; i++){
char aux = stringAr[i];
stringAr[i] = stringAr[length-i-1];
stringAr[length-i-1]= aux;
}
return stringAr;
}
private static Set<String> createDictionary() {
Set<String> dictionary = new HashSet<>();
dictionary.add("madam");
dictionary.add("nurses");
dictionary.add("run");
return dictionary;
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;
public class PalindromUtil {
public static String constructPalindrome(String input) {
if (input == null || input.length() <= 0)
return null;
int length = input.length();
Set<Integer> numberOfUniqChars = new HashSet<Integer>();
int[] ascii = new int[256];
String copy = new String(input);
char[] in = copy.toCharArray();
char uniq = in[0];
for (char c : in) {
if (numberOfUniqChars.add((int) c)) {
uniq = c;
}
ascii[c]++;
}
if (numberOfUniqChars.size() == 1)
return input;
if (numberOfUniqChars.size() > ((length / 2) + 1))
return "cannot construct palindrome for " + input;
int i = 0;
int j = length - 1;
for (Integer o : numberOfUniqChars) {
in[i++] = (char) o.intValue();
in[j--] = (char) o.intValue();
}
if(length%2 != 0) {
in[length / 2] = uniq;
}
if (!canBePalin(in, ascii, numberOfUniqChars))
return "cannot construct palindrome for " + input;
return new String(in);
}
private static boolean canBePalin(char[] in, int[] ascii, Set<Integer> numberOfUniqChars) {
if (in == null)
return false;
if (numberOfUniqChars.size() == 1 || numberOfUniqChars.size() == 2)
return true;
int[] ascii2 = new int[256];
for (char c : in) {
ascii2[c]++;
}
for (char c : in) {
if (ascii2[c] != ascii[c])
return false;
}
return true;
}
public static Vector<String> constructPalindrom(Vector<String> input) {
Vector<String> temp = new Vector<String>();
for (String in : input) {
temp.add(constructPalindrome(in));
}
return temp;
}
public static void main(String[] args) {
Vector<String> input = new Vector<String>();
input.add("buhuuu");
input.add("abcbca");
input.add("aaaaaab");
input.add("abbabbc");
input.add("aaaab");
input.add("abcdedcba");
input = constructPalindrom(input);
for (String out : input) {
System.out.println(" " + out);
}
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;
public class PalindromUtil {
public static String constructPalindrome(String input) {
if (input == null || input.length() <= 0)
return null;
int length = input.length();
Set<Integer> numberOfUniqChars = new HashSet<Integer>();
int[] ascii = new int[256];
String copy = new String(input);
char[] in = copy.toCharArray();
char uniq = in[0];
for (char c : in) {
if (numberOfUniqChars.add((int) c)) {
uniq = c;
}
ascii[c]++;
}
if (numberOfUniqChars.size() == 1)
return input;
if (numberOfUniqChars.size() > ((length / 2) + 1))
return "cannot construct palindrome for " + input;
int i = 0;
int j = length - 1;
for (Integer o : numberOfUniqChars) {
in[i++] = (char) o.intValue();
in[j--] = (char) o.intValue();
}
if(length%2 != 0) {
in[length / 2] = uniq;
}
if (!canBePalin(in, ascii, numberOfUniqChars))
return "cannot construct palindrome for " + input;
return new String(in);
}
private static boolean canBePalin(char[] in, int[] ascii, Set<Integer> numberOfUniqChars) {
if (in == null)
return false;
if (numberOfUniqChars.size() == 1 || numberOfUniqChars.size() == 2)
return true;
int[] ascii2 = new int[256];
for (char c : in) {
ascii2[c]++;
}
for (char c : in) {
if (ascii2[c] != ascii[c])
return false;
}
return true;
}
public static Vector<String> constructPalindrom(Vector<String> input) {
Vector<String> temp = new Vector<String>();
for (String in : input) {
temp.add(constructPalindrome(in));
}
return temp;
}
public static void main(String[] args) {
Vector<String> input = new Vector<String>();
input.add("buhuuu");
input.add("abcbca");
input.add("aaaaaab");
input.add("abbabbc");
input.add("aaaab");
input.add("abcdedcba");
input = constructPalindrom(input);
for (String out : input) {
System.out.println(" " + out);
}
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Vector;
public class PalindromUtil {
public static String constructPalindrome(String input) {
if (input == null || input.length() <= 0)
return null;
int length = input.length();
Set<Integer> numberOfUniqChars = new HashSet<Integer>();
int[] ascii = new int[256];
String copy = new String(input);
char[] in = copy.toCharArray();
char uniq = in[0];
for (char c : in) {
if (numberOfUniqChars.add((int) c)) {
uniq = c;
}
ascii[c]++;
}
if (numberOfUniqChars.size() == 1)
return input;
if ( numberOfUniqChars.size() > ((length/2)+1))
return "cannot construct palindrome for " + input;
if (length % 2 == 0) {
int i = 0;
int j = length - 1;
for (Integer o : numberOfUniqChars) {
in[i++] = (char) o.intValue();
in[j--] = (char) o.intValue();
}
} else {
int i = 0;
int j = length - 1;
in[length / 2] = uniq;
for (Integer o : numberOfUniqChars) {
if (((char) o.intValue()) != uniq) {
in[i++] = (char) o.intValue();
in[j--] = (char) o.intValue();
}
}
}
if(!canBePalin(in, ascii, numberOfUniqChars)) return "cannot construct palindrome for " + input;
return new String(in);
}
private static boolean canBePalin(char[] in, int[] ascii, Set<Integer> numberOfUniqChars) {
if(in == null) return false;
if(numberOfUniqChars.size() == 1 || numberOfUniqChars.size() == 2) return true;
int[] ascii2 = new int[256];
for(char c : in){
ascii2[c]++;
}
for(char c:in) {
if(ascii2[c] != ascii[c]) return false;
}
return true;
}
public static Vector<String> constructPalindrom(Vector<String> input) {
Vector<String> temp = new Vector<String>();
for(String in:input){
temp.add(constructPalindrome(in));
}
return temp;
}
public static void main(String[] args) {
Vector<String> input = new Vector<String>();
input.add("buhuuu");
input.add("abcbca");
input.add("aaaaaab");
input.add("abbabbc");
input.add("aaaab");
input.add("abcdedcba");
input = constructPalindrom(input);
for(String out:input) {
System.out.println(" " + out);
}
}
}
public static String[] reArrangeString(String[] input) {
String[] response = new String[input.length];
for (int i = 0; i < input.length; i++) {
response[i] = checkPalindrome(input[i]);
System.out.println(input[i] + ":" + response[i]);
}
return response;
}
public static String checkPalindrome(final String inputString) {
String response = null;
if (inputString != null && inputString.length() > 0) {
char[] arrayChr = inputString.toCharArray();
Arrays.sort(arrayChr);
List<Character> indiv = new ArrayList<Character>();
Stack<Character> stackChr = new Stack<Character>();
for (char c : arrayChr) {
if (!stackChr.isEmpty()) {
if (c == stackChr.peek()) {
stackChr.pop();
} else {
if (inputString.length() % 2 != 0) {
indiv.add(stackChr.pop());
stackChr.push(c);
if (indiv.size() > 1)
return "-1";
} else {
return "-1";
}
}
} else {
stackChr.push(c);
}
}
if (!stackChr.isEmpty())
indiv.add(stackChr.pop());
if (indiv.size() == 1) {
response = convertToPalindrome(arrayChr, indiv.get(0));
} else {
response = convertToPalindrome(arrayChr, '\u0000');
}
} else {
return "-1";
}
return response;
}
public static String convertToPalindrome(final char[] arrayChr,
char indivChar) {
Stack<Character> arrangeChar = new Stack<Character>();
StringBuffer buff = new StringBuffer();
Queue<Character> queue = new LinkedList<Character>();
for (char c : arrayChr) {
if (indivChar != c)
queue.add(c);
}
while (!queue.isEmpty()) {
buff.append(queue.poll());
arrangeChar.push(queue.poll());
}
if (indivChar != '\u0000') {
buff.append(indivChar);
}
while (!arrangeChar.isEmpty()) {
buff.append(arrangeChar.pop());
}
return buff.toString();
}
Please give me your suggestion. its working fine. Can i right like this in interview
public class PalindromeCheck {
public static void main(String[] args) {
String[] inputStringArr = {"abb","level"};
for(String input:inputStringArr) {
char[] inputArr = input.toCharArray();
int j = input.length()-1;
boolean result = true;
for(int i=0; i<input.length(); i++) {
if(inputArr[i]!=inputArr[j]){
result = false;
break;
}
j--;
}
if(result) {
System.out.println("The "+input+" - palindrome is possible");
} else {
System.out.println("The "+input+" - palindrome is not possible");
}
}
}
}
Working fine. Please suggest, is this right standard for interview?
public class PalindromeCheck {
public static void main(String[] args) {
String[] inputStringArr = {"abb","level"};
for(String input:inputStringArr) {
char[] inputArr = input.toCharArray();
int j = input.length()-1;
boolean result = true;
for(int i=0; i<input.length(); i++) {
if(inputArr[i]!=inputArr[j]){
result = false;
break;
}
j--;
}
if(result) {
System.out.println("The "+input+" - palindrome is possible");
} else {
System.out.println("The "+input+" - palindrome is not possible");
}
}
}
}
Its working fine. let me know is this right way?
public class PalindromeCheck {
public static void main(String[] args) {
String[] inputStringArr = {"abb","level"};
for(String input:inputStringArr) {
char[] inputArr = input.toCharArray();
int j = input.length()-1;
boolean result = true;
for(int i=0; i<input.length(); i++) {
if(inputArr[i]!=inputArr[j]){
result = false;
break;
}
j--;
}
if(result) {
System.out.println("The "+input+" is palindrome possible");
} else {
System.out.println("The "+input+" palindrome is not possible");
}
}
}
}
std::string createPalindrome(const std::string& data)
{
std::string palindrome(data);
std::vector<int> repeatCounter(256, 0);
bool unevenFound = false;
bool validPalindrome = true;
for(int i = 0; i < data.length(); ++i)
{
repeatCounter[data[i]]++;
}
int ctr = 0;
int midPoint = (data.length() / 2);
for(int i = 0; i < repeatCounter.size(); ++i)
{
if(repeatCounter[i] <= 0)
continue;
if(repeatCounter[i] % 2 && unevenFound)
{
validPalindrome = false;
break;
}
if(repeatCounter[i] % 2 && !unevenFound)
{
unevenFound = true;
repeatCounter[i]--;
palindrome[midPoint] = i;
}
for(int j = 0; j < repeatCounter[i]/2; ++j)
{
palindrome[ctr] = i;
palindrome[data.length() - ctr - 1] = i;
ctr++;
}
}
return validPalindrome ? palindrome : data;
}
std::string createPalindrome(const std::string& data)
{
std::string palindrome(data);
std::vector<int> repeatCounter(256, 0);
bool unevenFound = false;
bool validPalindrome = true;
for(int i = 0; i < data.length(); ++i)
{
repeatCounter[data[i]]++;
}
int ctr = 0;
int midPoint = (data.length() / 2);
for(int i = 0; i < repeatCounter.size(); ++i)
{
if(repeatCounter[i] <= 0)
continue;
if(repeatCounter[i] % 2 && unevenFound)
{
validPalindrome = false;
break;
}
if(repeatCounter[i] % 2 && !unevenFound)
{
unevenFound = true;
repeatCounter[i]--;
palindrome[midPoint] = i;
}
for(int j = 0; j < repeatCounter[i]/2; ++j)
{
palindrome[ctr] = i;
palindrome[data.length() - ctr - 1] = i;
ctr++;
}
}
return validPalindrome ? palindrome : data;
}
package System.out;
import java.util.Arrays;
public class Palindrome {
public char[] sortString(String str)
{
char ch[]=str.toCharArray();
for(int i=0;i<ch.length;i++){
for(int j=0;j<ch.length-1;j++)
{
char first=ch[j];
char second=ch[j+1];
if(first>second){
swap(j,j+1,ch);
}
}
}
return ch;
}
public void swap(int i,int j, char[] cc){
char first=cc[i];
char second=cc[j];
cc[i]=second;
cc[j]=first;
}
public static void main(String[] args) {
String ss = "tenet".toLowerCase();
//r o t a v a t o r
Palindrome p = new Palindrome();
String ss1 = String.valueOf(p.sortString(ss));
System.out.println(ss1);
char cc[]=ss1.toCharArray();
int hi=cc.length;
int middle=hi/2;
char[] paliStringChar=new char[cc.length];
int isPali=-1;
int leftIndex = 0;
int i=0;
int j=hi-1;
while(leftIndex<hi-1){
if(i==middle){
i++;
}
if(cc[leftIndex]==cc[leftIndex+1]){
paliStringChar[i++]=cc[leftIndex];
paliStringChar[j--] = cc[leftIndex+1];
leftIndex=leftIndex+2;
}
else{
paliStringChar[middle]=cc[leftIndex];
leftIndex++;
isPali++;
}
}
if(leftIndex==hi-1){
paliStringChar[middle]=cc[leftIndex];
}
if(isPali==1){
System.out.println(String.valueOf(String.valueOf(paliStringChar)+" is NOT a Palindrome String "));
}
else{
System.out.println(String.valueOf(String.valueOf(paliStringChar)+" is Palindrome String "));
}
}
}
import java.util.Arrays;
public class Palindrome {public char[] sortString(String str)
{char ch[]=str.toCharArray();
for(int i=0;i<ch.length;i++){
for(int j=0;j<ch.length-1;j++)
{
char first=ch[j];
char second=ch[j+1];
if(first>second){
swap(j,j+1,ch);
}
}
}
return ch;
}
public void swap(int i,int j, char[] cc){
char first=cc[i];
char second=cc[j];
cc[i]=second;
cc[j]=first;
}
public static void main(String[] args) {
String ss = "tenet".toLowerCase();
//r o t a v a t o r
Palindrome p = new Palindrome();
String ss1 = String.valueOf(p.sortString(ss));
System.out.println(ss1);
char cc[]=ss1.toCharArray();
int hi=cc.length;
int middle=hi/2;
char[] paliStringChar=new char[cc.length];
int isPali=-1;
int leftIndex = 0;
int i=0;
int j=hi-1;
while(leftIndex<hi-1){
if(i==middle){
i++;
}
if(cc[leftIndex]==cc[leftIndex+1]){
paliStringChar[i++]=cc[leftIndex];
paliStringChar[j--] = cc[leftIndex+1];
leftIndex=leftIndex+2;
}
else{
paliStringChar[middle]=cc[leftIndex];
leftIndex++;
isPali++;
}
}
if(leftIndex==hi-1){
paliStringChar[middle]=cc[leftIndex];
}
if(isPali==1){
System.out.println(String.valueOf(String.valueOf(paliStringChar)+" is NOT a Palindrome String "));
}
else{
System.out.println(String.valueOf(String.valueOf(paliStringChar)+" is Palindrome String "));
}
}
}
package package1;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Palindrome {
public List<String> pal(String[] old) {
List<String> newList = new ArrayList<String>();
for (String str : old) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(str.charAt(i))) {
map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
}
else {
map.put(str.charAt(i), 1);
}
}
Set<Character> keys = map.keySet();
int singleCount = 0;
Boolean isPalin = true;
for (Character ch : keys) {
if (map.get(ch) % 2 != 0) {
singleCount++;
if (singleCount == 2) {
isPalin = false;
break;
}
}
}
if (isPalin) {
newList.add(str);
}
}
return newList;
}
public static void main(String args[]) {
Palindrome test = new Palindrome();
String[] list = { "test", "appall", "inkink", "janja" };
System.out.println(test.pal(list));
}
}
package package1;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Palindrome {
public List<String> pal(String[] old) {
List<String> newList = new ArrayList<String>();
for (String str : old) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(str.charAt(i))) {
map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
}
else {
map.put(str.charAt(i), 1);
}
}
Set<Character> keys = map.keySet();
int singleCount = 0;
Boolean isPalin = true;
for (Character ch : keys) {
if (map.get(ch) % 2 != 0) {
singleCount++;
if (singleCount == 2) {
isPalin = false;
break;
}
}
}
if (isPalin) {
newList.add(str);
}
}
return newList;
}
public static void main(String args[]) {
Palindrome test = new Palindrome();
String[] list = { "test", "appall", "inkink", "janja" };
System.out.println(test.pal(list));
}
}
public static void main2(){
String[] inputStrings ={"xxyy","ddd", "deeee", "weee", "fjff", "rrrraaffttt","ddzz"};
for( String input : inputStrings){
int [] counter = new int[26];
for( char c : input.toCharArray()){
counter[(int)c -97]++;
}
int len = input.length();
int j =0;
int k=0;
for (int i=0;i<25;i++){
if(counter[i]%2 !=0){
j++;
if (j>1) break;
k=i;
}
}
if (((len%2!=0) && (j!=1))||((len%2==0) && (j!=0)) )
System.out.println("no");
else{
int[] temp = new int[len];
int n =0;
if(len%2!=0)
temp[(len -1)/2]=k;
for (int i=0;i<26;i++){
if(counter[i]!=0){
int ti = counter[i]/2;
for (int ii=n;ii<n+ti;ii++){
temp[ii] =i;
temp[len-1 -ii]=i;
}
n= n+ti;
}
}
StringBuilder sb = new StringBuilder();
for (int i=0; i<len; i++){
char c = (char)(temp[i]+97);
sb.append(c);
}
System.out.println( sb.toString());
}
}
}
public static void main2(){
String[] inputStrings ={"xxyy","ddd", "deeee", "weee", "fjff", "rrrraaffttt","ddzz"};
for( String input : inputStrings){
int [] counter = new int[26];
for( char c : input.toCharArray()){
counter[(int)c -97]++;
}
int len = input.length();
int j =0;
int k=0;
for (int i=0;i<25;i++){
if(counter[i]%2 !=0){
j++;
if (j>1) break;
k=i;
}
}
if (((len%2!=0) && (j!=1))||((len%2==0) && (j!=0)) )
System.out.println("no");
else{
int[] temp = new int[len];
int n =0;
if(len%2!=0)
temp[(len -1)/2]=k;
for (int i=0;i<26;i++){
if(counter[i]!=0){
int ti = counter[i]/2;
for (int ii=n;ii<n+ti;ii++){
temp[ii] =i;
temp[len-1 -ii]=i;
}
n= n+ti;
}
}
StringBuilder sb = new StringBuilder();
for (int i=0; i<len; i++){
char c = (char)(temp[i]+97);
sb.append(c);
}
System.out.println( sb.toString());
}
}
}
private static void convertPalindrome(String[] input){
if(input==null){
return;
}
for(int i=0;i<input.length;i++){
char[] chars=input[i].toCharArray();
int[] occurances=new int[26];
int oddCount=0;
for(int j=0;j<chars.length;j++){
int ascii=chars[j];
occurances[ascii-97]++;
if(occurances[ascii-97]%2!=0){
oddCount++;
}else{
oddCount--;
}
}
if(oddCount>1){
input[i]="-1";
}else{
String palindrome="";
Character oddchar=null;
Character foundChar=null;
for(int k=0;k<occurances.length;k++){
if(occurances[k]!=0){
if(occurances[k]==1){
oddchar=(char)(k+97);
}else{
foundChar=(char)(k+97);
for(int l=1;l<=occurances[k]/2;l++){
palindrome+=foundChar;
}
}
}
}
if(null!=oddchar){
palindrome+=oddchar;
}
for(int m=occurances.length-1;m>=0;m--){
if(occurances[m]!=0){
if(occurances[m]!=1){
foundChar=(char)(m+97);
for(int l=1;l<=occurances[m]/2;l++){
palindrome+=foundChar;
}
}
}
}
input[i]=palindrome;
}
}
}
import java.util.Arrays;
import java.util.stream.Collectors;
public class Test {
public static void main(String[] args){
String[] arra=new String[4];
arra[0]="malayalam";
arra[1]="dad";
arra[2]="check";
arra[3]="book";
Object[] palindrome=checkpalindrome(arra);
for(int i=0;i<palindrome.length;i++) {
System.out.println(palindrome[i]);
}
}
private static Object[] checkpalindrome(String[] arra) {
return Arrays.asList(arra).stream().map(mapper->{
String reversedString=new StringBuilder(mapper).reverse().toString();
return reversedString.equalsIgnoreCase(mapper)? mapper :-1;
}).collect(Collectors.toList()).toArray();
}
}
}
O(nm) runtime complexity where n is the number of strings and m is the average size of the strings. O(nm) memory complexity too.
A quick way to determine if a string can be a palindrome is to:
1. Count the occurrences of each character in the string
2. Iterate from the 'a' to the 'z' counts. add half of the count of each character to the string. If the character has an odd count, remember it. If there were other characters with an odd count, then there isn't a palindrome so return null
3. If any odd characters, add it now
4. Iterate from the 'z' to the 'a' counts and add half the count of each character to the string
5. return the string
- zortlord September 14, 2015//If all palindromes couldn't be found, return null public static String[] palindromify(String[] strs){ if(strs == null){ return null; } String[] results = new String[strs.length]; for(int i = 0; i < strs.length; i++){ int[] counts = genCount(strs[i]); StringBuilder builder = new StringBuilder(); int middle = -1; for(int j = 0; j < 26; j++){ int count = counts[j]; if(count % 2 == 1){ if(middle > 0){ return null; } middle = j } count /= 2; counts[j] = count; for(int k = 0; k < count; k++){ builder.append((char)('a'+j)); } } if(middle >= 0){ builder.append((char)('a'+middle));\ } for(int j = 25; j >= 0; j--){ int count = counts[j]; for(int k = 0; k < count; k++){ builder.append((char)('a'+j)); } } results[i] = builder.toString(); } return results; } private static int[] genCount(String str){ int[] counts = new int[26]; for(int i = 0; i < str.length(); i++){ counts[str.charAt(i)-'a']++; } return counts; }