Problem1 :

Given a string S, find for all substrings of S the minimum cost of operations needed to make each of its substring a palindrome. In one operation you can,

1) Either rearrange the substring with cost 0 or, 2) Replace a character with cost 1

I came up with a O(26 * N * N) solution, but the constraints N <= 1e5. How to solve it?

Problem2:

Given an array weight[] and profit[] (similar to Knapsack Problem) you are also given the size of the knapsack W. you need to find a subset whose bitwise OR is <= W and the profits are maximum. Constraints : N <= 1e5, weight[i] <= 1e9, W <= 1e9, profit[] <= 1e9.

Thanks for the help in advance!!!