Skip to content

Instantly share code, notes, and snippets.

@cyrilnoah1
Last active November 28, 2019 03:27
Show Gist options
  • Save cyrilnoah1/f197acf93694dc72d76e06b35121a5f0 to your computer and use it in GitHub Desktop.
Save cyrilnoah1/f197acf93694dc72d76e06b35121a5f0 to your computer and use it in GitHub Desktop.
Minimum sum of squares of cha.racter counts in a given string after removing k characters
import kotlin.system.*
import kotlin.contracts.*
import java.util.*
fun main() {
print(MinCharSquareSum().getResult("aabaa", 0))
}
class MinCharSquareSum {
fun getResult(input : String, k: Int): Int{
val strLength = input.length
if(k >= strLength){
return 0
}
fun result() : Int{
fun calculateFrequency(): IntArray{
val arr = IntArray(26)
for(i in 0 until strLength){
arr[input.get(i) - 'a']++
}
return arr
}
fun calculatePriority() : PriorityQueue<Int>{
val f = calculateFrequency()
val p = PriorityQueue(IntCompare())
for (i in 0 until f.size) if(f[i] != 0) p.add(f[i])
return p
}
val p = calculatePriority()
for(i in 0 until k){
var temp = p.peek()
p.poll()
temp -= 1
p.add(temp)
}
var res = 0
while(p.isNotEmpty()){
var temp = p.peek()
res += temp * temp
p.poll()
}
return res
}
return result()
}
inner class IntCompare : Comparator<Int>{
override fun compare(prev: Int, next: Int): Int{
return when{
prev > next -> -1
prev < next -> 1
else -> 0
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment