问题 1168. -- Water Problem: LCS## 1168: Water Problem: LCS

时间限制: 2 Sec 内存限制: 128 MB

提交: 122 解决: 40

[提交][状态][讨论版]## 题目描述

Wise cyt has got a string **S** with **N **(1 ≤ N ≤ 10^5 ) characters. All the characters of **S** are lowercase or uppercase English letters. Now he challenges Xingxing to find out a string **T** of length **N** such that the length of the LCS (Longest Common Subsequence) of **S** and **T** is minimum. **T** also should be consisted of lowercase or uppercase English letters only. Now it is Xingxing’s problem to find out the string **T**. But you need to print the minimum length of such LCS given that Xingxing has found **T** correctly.

## 输入

Input file starts with a single integer** T** (1 ≤ T ≤ 50), **T** test cases following. Each of the next** T **test cases has one string** S** on a line.

## 输出

For each case print your output in format, ‘Case **X**: **Y** ’, on a single line where **X** denotes the case number starting from 1 and **Y** denotes the length of the shortest possible **LCS**.

## 样例输入

2
ab
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

## 样例输出

Case 1: 0
Case 2: 1

## 提示

Subsequence can be not constant.

## 来源

[提交][状态][讨论版]