6001: 【DFS/BFS】美团2023秋招-小美的字符串变换
金币值：
1
时间限制：2.000 s
内存限制：128 M
正确：25
提交：39
正确率：64.10% 命题人：
题目描述
小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x*y=n，即每y个字符换行，共x行）。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？
注：我们定义，上下左右四个方向相邻的相同字符是连通的。
输入格式
第一行输入一个正整数n，代表字符串的长度。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
1 <= n <= 10^4
输出格式
输出一个整数表示最小权值。
输入样例 复制
9
aababbabb输出样例 复制
2提示
平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。