בהינתן מחרוזת תווים \(st\), נגדיר תת-סדרה (sub-sequence) של המחרוזת כמחרוזת שנשארה לאחר שהורדו ממנה חלק מהתווים.
למשל, אם המחרוזת המקורית \(st = \text{"abcde"}\) אז כל אחת מהמחרוזות להלן היא תת-סדרה של \(st\) (לא כתבנו כאן את כל האפשרויות):
"ab", "ce", "acd", "d", "abcde", "" (the empty string)

שימו לב שתת-סדרה (sub-sequence) אינה תת-מחרוזת (sub-string), ולכן התווים אינם צריכים להיות במיקום עוקב דווקא, אבל הסדר ביניהם צריך להיות כמו הסדר במחרוזת המקורית, ולא יכולים להיות תווים שלא היו במחרוזת המקורית. בפרט, המחרוזת המקורית והמחרוזת הריקה, שתיהן תת-סדרה של המחרוזת המקורית.
לכן, המחרוזות להלן אינן תת-סדרה של \(st\):
"ba", "cf", "edcba", "g"

בהינתן שלוש מחרוזות תווים \(st1, st2, st3\), נגדיר את התת-סדרה המשותפת הארוכה ביותר לשלוש המחרוזות, כמחרוזת תווים הארוכה ביותר שאפשר ליצור כאשר מורידים חלק מהתווים מכל אחת מהמחרוזות.

לדוגמא:

• אם המחרוזות הן: \(st1 = \text{"ABCBDAB"}, st2 = \text{"BDCABA"}, st3 = \text{"BADACB"}\)
  אז יש הרבה תת-סדרות משותפות לשלוש המחרוזות, למשל "AB", "BDA", אבל התת-סדרה הארוכה ביותר המשותפת לשלושתן היא "BDAB". התת-סדרה הזו מודגשת במחרוזות: \(st1 = \text{"ABC\textbf{BDAB}"}, st2 = \text{"\textbf{BD}C\textbf{AB}A"}, st3 = \text{"\textbf{B}A\textbf{DA}C\textbf{B}"}\)
• אם המחרוזות הן: \(st1 = \text{"ABCBDAB"}, st2 = \text{"XYZ"}, st3 = \text{"DC"}\)
  אז אין תת-סדרה משותפת. למעשה, התת-סדרה היחידה המשותפת לשלוש המחרוזות היא המחרוזת הריקה.

כתבו שיטה סטטית רקורסיבית המקבלת כפרמטרים שלוש מחרוזות תווים, ומחזירה את האורך של המחרוזת שמהווה תת-סדרה משותפת ארוכה ביותר של שלוש המחרוזות.
(LCS = Longest Common Subsequence)
אם אין שום תת-סדרה משותפת לשלוש המחרוזות, השיטה צריכה להחזיר את הערך 0.

חתימת השיטה היא:
public static int lcs (String st1, String st2, String st3)

הנחיות:

• השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות.
• מותר להשתמש בשיטות המחלקה String (charAt, length, substring) ובשיטות המחלקה Math (max, min) בלבד.
• אין צורך לדאוג ליעילות השיטה.