小美的字符串变换

[编程题]小美的字符串变换

小美拿到了一个长度为 $n$ 的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有 $x$ 行 $y$ 列，必须保证 $x*y=n$ ，即每 $y$ 个字符换行，共 $x$ 行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

第一行输入一个正整数，代表字符串的长度。
第二行输入一个长度为的、仅由小写字母组成的字符串。

输出一个整数表示最小权值。

示例1

输入

9
aababbabb

平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

来自：美团2023年秋招笔试...

难度：

0条回答 53收藏 1847浏览

小美的字符串变换

扫一扫，把题目装进口袋