Maximum subsequences

Consider a string $s$ of length $n$ that consists of lowercase Latin alphabetic characters. You are given an array $A$ of size 26 showing the value for each alphabet. You must output the subsequence of size $k$ whose sum of values is maximum.

If there are multiple subsequences available, then print the lexicographically smallest sequence. 

String $p$ is lexicographically smaller than string $q$ if $p$ is a prefix of $q$ and is not equal to $q$ or there exists $i$, such that $p_i\hspace{0.17em}<\hspace{0.17em}{q}_i$ and for all $j\hspace{0.17em}<\hspace{0.17em}i$ it is satisfied that $p_j\hspace{0.17em}=\hspace{0.17em}{q}_j$. For example, '$abc$' is lexicographically smaller than '$abcd$', '$abd$' is lexicographically smaller than '$abec$', and '$afa$' is not lexicographically smaller than '$ab$'.

Example:

Input :
6 3
cadbca
5 2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output: 
aca

Approach

Java

import java.util.HashMap;
import java.util.Map;

public class MaximumSubsequences {
    public static void main(String args[]) {
        int n = 6;
        int k = 3;
        String str = "cadbca";
        String[] vals = "5 2 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0".split(" ");
        // 26 letter array declaration
        int[] alp = new int[26];
        char[] alpha = new char[26];
        Map<Character, Integer> alphMap = new HashMap();
        Map<Character, Integer> alpFreq = new HashMap<Character, Integer>();
        // count frequenecy
        for (char a : str.toCharArray()) {
            alpFreq.put(a, alpFreq.getOrDefault(a, 0) + 1);
        }
        for (int j = 0; j < 26; j++) {
            alp[j] = Integer.parseInt(vals[j]);
            alpha[j] = (char) (97 + j);
            alphMap.put(alpha[j], alp[j]);
        }

        if (n == 1) {
            System.out.println(str);
        } else {

            // sorting descendint
            for (int p = 0; p < 26; p++) {
                for (int q = p + 1; q < 26; q++) {
                    if (alp[p] < alp[q]) {
                        int tmp = alp[q];
                        alp[q] = alp[p];
                        alp[p] = tmp;
                        char tch = alpha[q];
                        alpha[q] = alpha[p];
                        alpha[p] = tch;
                    }
                }
            }

            // finding characters required
            Map<Character, Integer> resultFreq = new HashMap<Character, Integer>();
            int s = 0;
            int c = 0;
            for (int a = k; a > 0;) {
                int freq = alpFreq.containsKey(alpha[s]) ? alpFreq.get(alpha[s]) : 0;
                a -= freq;
                while (freq > 0 && c < k) {
                    resultFreq.put(alpha[s], resultFreq.getOrDefault(alpha[s], 0) + 1);
                    c++;
                    freq--;
                }
                s++;
            }

            char[] resultArr = new char[k];
            int m = 0, o = 0;
            for (char f : str.toCharArray()) {
                m++;
                if (resultFreq.containsKey(f) && resultFreq.get(f) > 0) {
                    resultArr[0] = f;
                    resultFreq.put(f, resultFreq.get(f) - 1);
                    alpFreq.put(f, alpFreq.get(f) - 1);
                    break;
                }
            }
            // m++;
            for (; m < str.length() && o < k; m++) {
                if (resultFreq.containsKey(str.charAt(m))) {
                    if (resultFreq.get(str.charAt(m)) > 0) {
                        if (resultArr[o] > str.charAt(m)) {
                            if (resultFreq.get(str.charAt(m)) > 0
                                    && alpFreq.get(resultArr[o]) > resultFreq.get(resultArr[o])) {
                                int t = o - 1;
                                int freq = 1;
                                char tm = resultArr[o];
                                while (t >= 0 && resultArr[t] == tm && alpFreq.get(tm) >= resultFreq.get(tm) + 1) {
                                    freq++;
                                    resultArr[t + 1] = '\0';
                                    resultFreq.put(tm, resultFreq.get(tm) + 1);
                                    t--;
                                    o = t + 1;
                                }
                                if (freq > 1) {
                                    if (freq <= alpFreq.get(tm) && alpFreq.get(tm) >= resultFreq.get(tm) + 1) {
                                        resultArr[t + 1] = str.charAt(m);
                                        resultFreq.put(tm, resultFreq.get(tm) + 1);
                                        resultFreq.put(str.charAt(m), resultFreq.get(str.charAt(m)) - 1);
                                        alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                                    } else {
                                        o++;
                                        resultArr[o] = str.charAt(m);
                                        resultFreq.put(str.charAt(m), resultFreq.get(str.charAt(m)) - 1);
                                        alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                                    }
                                } else {
                                    resultFreq.put(tm, resultFreq.get(tm) + 1);
                                    resultArr[o] = str.charAt(m);
                                    resultFreq.put(str.charAt(m), resultFreq.get(str.charAt(m)) - 1);
                                    alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                                }
                            } else {
                                o++;
                                resultArr[o] = str.charAt(m);
                                resultFreq.put(str.charAt(m), resultFreq.get(str.charAt(m)) - 1);
                                alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                            }
                        } else {
                            o++;
                            resultArr[o] = str.charAt(m);
                            resultFreq.put(str.charAt(m), resultFreq.get(str.charAt(m)) - 1);
                            alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                        }
                    } else {
                        if (resultArr[o] == str.charAt(m)) {
                            resultArr[o] = str.charAt(m);
                            alpFreq.put(str.charAt(m), alpFreq.get(str.charAt(m)) - 1);
                        }
                    }
                }
            }

            for (char x : resultArr) {
                System.out.print(x);
            }
            System.out.println("");
        }
    }

}