At the very latest, four weeks before the start of the new Congress - unless no session of Congress is scheduled before the expiry of the term, in which case no special election is required.
Section 100.101 (4) of the Florida statutes states that a special election must be held if a vacancy arises in the office of a member from Florida of the House of Representatives of Congress.
Section 100.111 (2) sets out how the dates for the special election must be scheduled by the Governor in consultation with the Secretary of State. In particular, the Governor must allow for a primary election and a special election, and the dates fixed "shall provide a minimum of 2 weeks between each election". It also states:
If a vacancy in office occurs in any district in the state Senate or House of Representatives or in any congressional district, and no session of the Legislature, or session of Congress if the vacancy is in a congressional district, is scheduled to be held during the unexpired portion of the term, the Governor is not required to call a special election to fill such vacancy.
Section 100.111 (2)(a) further stipulates that there must be a period of at least 14 days between the last day to qualify for a primary election and the election itself, so a total of four weeks between the last day to qualify and the special election.
Section 99.095 would usually require candidates who wish to enter a primary election without a qualifying fee or party assessment to submit a petition at least 28 days prior to said election, but this deadline can be altered by the Department of State in accordance with Section 100.111 (2)(c):
The dates for a candidate to qualify by the petition process pursuant to s. 99.095 in such special primary or special election shall be fixed by the Department of State. In fixing such dates the Department of State shall take into consideration and be governed by the practical time limitations. Any candidate seeking to qualify by the petition process in a special primary election shall obtain 25 percent of the signatures required by s. 99.095.
The absolute minimum, then, is the 14 days required to allow candidates to qualify for the primary election, followed by a two-week gap between the primary election and the special election; a total of four weeks.