Untitled

mail@pastecode.io avatar
unknown
java
a year ago
1.4 kB
1
Indexable
Never
import java.util.*;

public class Palindrome {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        sc.nextLine();
        String s = sc.nextLine();
        int[][] queries = new int[q][3];

        for (int i = 0; i < q; i++) {
            queries[i][0] = sc.nextInt();
            queries[i][1] = sc.nextInt();
            queries[i][2] = sc.nextInt();
        }

        System.out.println(canMakePaliQueries(s, n, queries));
    }

    public static int canMakePaliQueries(String s, int n, int[][] queries) {
        List<Boolean> res = new ArrayList<>();

        for (int[] query : queries) {
            res.add(canMakePal(s, query[0] - 1, query[1] - 1, query[2]));
        }

        int ans = 0;
        for (int i = 0 ; i < res.size(); i++) {
            if (res.get(i)) {
                ans = (ans + (int) Math.pow(2, i + 1)) % 1000000007;
            }
        }
        return ans;
    }

    private static boolean canMakePal(String s, int start, int end, int max) {
        if (max >= 13) return true;
        Set<Character> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            if (!set.add(s.charAt(i))) set.remove(s.charAt(i));
        }
        return max >= set.size()/2;
    }
}