Last active
November 28, 2019 03:27
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode 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