Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

package com.examples.ajay;

public class MaxSumNoAdjacentElement {

  private static int max(int i, int j) {

// TODO Auto-generated method stub

if(i < j) return j;

else return i;

}

private static void findSum(int[] array) {

// TODO Auto-generated method stub

int inclusive = array[0]; 
  // Max sum including current element. (If current included, prev     have to be excluded)

int exclusive = 0;
  // Max sum excluding current element : max (prev-incl, prev-excl) 

for(int i = 1; i< array.length; i++){

int temp = inclusive;

inclusive = exclusive + array[i];

exclusive = max(exclusive, temp);

}

System.out.println("Result : "+ max(inclusive, exclusive));

}

public static void main(String[] args) {

// TODO Auto-generated method stub

int array[] = {5, 5, 10, 40, 50, 35};

findSum(array);

}

}

Game of Thrones - I

Problem Statement

Dothraki are planning an attack to usurp King Robert's throne. King Robert learns of this conspiracy from Raven and plans to lock the single door through which the enemy can enter his kingdom.

But, to lock the door he needs a key that is an anagram of a certain palindrome string.

The king has a string composed of lowercase English letters. Help him figure out whether any anagram of the string can be a palindrome or not.

Input Format 
A single line which contains the input string.

Constraints 
1≤ length of string ≤105 
Each character of the string is a lowercase English letter.

Output Format 
A single line which contains YES or NO in uppercase.

Sample Input : 01

aaabbbb

Sample Output : 01

YES

Explanation 
A palindrome permutation of the given string is bbaaabb. 

Sample Input : 02

cdefghmnopqrstuvw

Sample Output : 02

NO

Explanation 
You can verify that the given string has no palindrome permutation. 

Sample Input : 03

cdcdcdcdeeeef

Sample Output : 03

YES

Explanation 
A palindrome permutation of the given string is ddcceefeeccdd

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        String entry = in.next();
        int[] frequency = new int[26];
        for(int i =0; i<entry.length(); i++){
            char ch = entry.charAt(i);
            frequency[ch - 'a']++;
        }
        int countOdd = 0;
        for(int i = 0; i < 26 ; i++){
            if(frequency[i] % 2 != 0){
                countOdd++;
            }
        }
        if(countOdd > 1) System.out.println("NO");
        else System.out.println("YES");
    }
}

Sherlock and Anagrams

Problem Statement

Given a string S, find the number of "unordered anagrammatic pairs" of substrings.

Input Format

First line contains T, the number of testcases. Each testcase consists of string S in one line.

Constraints 
1≤T≤10 
2≤length(S)≤100 
String S contains only the lowercase letters of the English alphabet.

Output Format

For each testcase, print the required answer in one line.

Sample Input

2
abba
abcd

Sample Output

4
0

Explanation

Let's say S[i,j] denotes the substring Si,Si+1,⋯,Sj.

testcase 1: 
For S=abba, anagrammatic pairs are: {S[1,1],S[4,4]}, {S[1,2],S[3,4]}, {S[2,2],S[3,3]}and {S[1,3],S[2,4]}.

testcase 2: 
No anagrammatic pairs.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
// TODO Auto-generated method stub
   Scanner in = new Scanner(System.in);
       int N = in.nextInt();
       Map<String, Integer> frequency = new HashMap<String, Integer>();
       while(N > 0){
        frequency.clear();
           String entry = in.next();
           int pairCount = 0;
           for(int i = 0; i < entry.length(); i++){
               for(int j = i+1; j <= entry.length(); j++){
                char[] keySeq = entry.substring(i, j).toCharArray();
                Arrays.sort(keySeq);
                String key = new String(keySeq);
                if(frequency.containsKey(key)){
                frequency.put(key, frequency.get(key)+1);
                }else{
                frequency.put(key, 1);
                }
               }
           }
           int sum = 0;
           Set<String> keys = frequency.keySet();
           for(String key : keys){
            sum += (frequency.get(key)*(frequency.get(key)-1))/2;
           }
           System.out.println(sum);
           N--;
       }
}
}